Recurrence relations (Big-O notation)

Question

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)?

Answer 1

You need to evaluate how many calls there are caused by function of $n$. How many times is the loop executed? What happens inside the loop? If $T(n)$ is the time complexity of the function, you have $T(n)=$(number of times through the loop)*(time complexity of what happens in the loop). Can you figure these out?

Answer 2

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.