Finding asymptotic complexity of recurrence relations

Question

Recently I came across the fact that the recurrence relation

$$T_1(n) = T_1(n-1) + T_1(n-2)$$

has the time complexity of $O(2^n)$, despite the fact that the recursion tree is not full binary tree as in case of $T_2(n) = 2\times T_2(n-1)$

Now I have come across two more recurrences:

1. $T_3(n)=2T_3(n/2) + n$
2. $T_4(n) =T_4(n/5) + T_4(7n/10) + n$

The recursion tree of first one forms complete binary tree, while that of 2nd dont. So I thought both will have same time complexity as in case of $T_1$ and $T_2$. But that was not the case. 1st recurrence have time complexity of $O(n \log{n})$ and second, $O(n)$!

Why is it so? Is it because, the difference between the rate at which branches of recursion tree of $T_1$ which terminate early and which terminate late is not much, but in $T_4$ the difference is more?

Answer 1

The first recurrence you are quoting is the Fibonacci recurrence, it's solution is exponential, but not $2^n$ (although it is $O(2^n)$).

As for the actual question, the coefficient in front of the recurrence has a lot of meaning. The main features you need to pay attention to are

• In $T_1, T_2$ the decrease of the argument each iteration is by subtracting constants, such things usually end up in exponential solutions
• In $T_3,T_4$ the decrease of the argument is by dividing by a constant instead, these tend to be in polynomial solutions, very often with an extra logarithmic factor, like $n \ln n$ for example for $T_3$
• The constant in the front of the term is important also

Have you seen the Master Theorem yet?

Answer 2

This is a dynamic programming problem. The issue is that a direct evaluation involves a lot of re-computing, which can be completely avoided. In the case of $T_1$, this can make the time complexity as high as $\mathcal O(2^n)$, even though you can reduce it down to $\mathcal O(n)$ using tail recursion, since the recursion tree only has $n$ nodes. The difference in what's needed to be computed differ drastically in these two cases. See here for a programmed example. We can show that it takes $\mathcal O(2^n)$ steps to compute $T_1$ directly by induction. Suppose $T_1(n-1)$ takes $\simeq2^{n-1}$ steps to compute, and $T_1(n-2)$ takes $\simeq2^{n-2}$ steps to compute. Then $T_1(n)$ takes $\simeq2^{n-1}+2^{n-2}<2^n$ steps to compute.

In the case of $T_3$, the time complexity should actually be $\mathcal O(\log n)$. Consider $n=2^3$ for example. To work out $T_3(2^3)$ we use $T_3(2^2),T_3(2^1),$ and $T_3(2^0)$, which is only 3 more cases to work out. In general, $T_3(n)$ takes $\log_2(n)$ more computations to evaluate, and hence $\mathcal O(\log n)$ complexity.

Analysis of $T_4$ is less obvious, but it can easily be affirmed by induction. If $T_4(n/5)$ takes $\simeq n/5$ steps to evaluate, and $T_4(7n/10)$ takes $\simeq7n/10$ steps to evaluate, then $T_4(n)$ takes $\simeq9n/10<n$ steps to evaluate. As a matter of fact, one can see that this gives the even better bound of $\mathcal O(\log n)$ for the time complexity, particularly about $\log_{10/9}(n)$ steps. As far as optimizing this one further, one would want to cache results to avoid repeated computations.