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)?
 A: 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?
A: 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.
A: Are you familiar with the Master Theorem? I'd look at using that rather than getting into the mess of solving the recurrence. Since a > 5, you'll get $\Theta(n^{log(n)})$ as your answer. Note with complexities, you can omit the base for the logarithm, as it can be treated as a constant. 
More on the Master Theorem: http://cse.unl.edu/~choueiry/S06-235/files/MasterTheorem-Handout.pdf
