<s>[INST] Recurrence relations (Big-O notation) Say I'm given a recursive function such as:
function(n) {

   if (n <= 1)
      return;

   int i;
   for(i = 0; i < n; i++) {
      function(0.8n)
   }
}

how would I go about applying recurrence relations to the find the Big-O run time
(as a function of n)?
 [/INST] I solved the recurrence relation as the following: $$\text{With: }0.8 = \frac{4}{5}$$
$$
\\
T(n) = \sum_{i = 0}^{n - 1}(T(\frac{4}{5}n) + c), \text{ with } T(n) = 1 \text{ when } n \leq 1
\\\\
T(n) = nT(\frac{4}{5}n) + nc
\\\\
T(n) = (\frac{4}{5})n^2T([\frac{4}{5}]^2n) + (\frac{4}{5})n^2c + nc
\\\\
T(n) = (\frac{4}{5})^2n^3T([\frac{4}{5}]^3n) + (\frac{4}{5})^2n^3c + (\frac{4}{5})n^2c + nc
\\
...
\\
T(n) = (\frac{4}{5})^{k - 1}n^kT([\frac{4}{5}]^kn) + c\sum_{i = 1}^{k}[\frac{4}{5}]^{i - 1}n^i
\\
\text{When } [\frac{4}{5}]^kn = 1, [\frac{4}{5}]^k = [\frac{1}{n}], k = log_{[\frac{4}{5}]}([\frac{1}{n}]), k = -log_{[\frac{4}{5}]}(n)
\\
T(n) = (\frac{4}{5})^{-log_{[\frac{4}{5}]}(n) - 1}n^{-log_{[\frac{4}{5}]}(n)}T(1) + c\frac{5n[(\frac{4}{5})^{-log_{[\frac{4}{5}]}(n)}n^{-log_{[\frac{4}{5}]}(n)} - 1]}{4n - 5}
\\
\text{Therefore, } T(n) \text{ } \in \text{ } \Theta (n^{-log_{[\frac{4}{5}]}(n)})
$$
I wrote a small c program which computes the number of calls of $function()$. and I found that when n = 10, the number of calls was 93616111.
I had to break the program when I executed it with n = 100; it took forever.
Note that the formula of the series above was deduced, thanks to WolframAlpha.
</s>