Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I have two recurrences:
$T_1(n) = 2 T_1(n-1) + n$ if $n > 1$, $1$ if $n = 1$
$T_2(n) = 2 T_2(\frac{n}{2}) + n^2$ if $n > 1$, $2$ if $n = 1$
Does this mean $T_1$ is better than $T_2$ because it has less operations to do?
Edit: I looked at the master theorem and found out that the 2nd one has an $O(n^2)$ runtime.
The simplest way is to solve both recurrence relations, and see whether one of them grows faster. In your case there is actually no need to do that, since we can observe that on the one hand $$ T_1(n) \geq 2T_1(n-1) \geq 2^2T_1(n-2) \geq \cdots \geq 2^{n-1}T(1) = 2^{n-1}, $$ and on the other hand $$ T_2(n) = O(n^2), $$ by the master theorem. This is enough to deduce that $T_2(n) = o(T_1(n))$, that is, $T_1(n)$ grows faster than $T_2(n)$.
I think before you use tools like the master theorem, you should be training your intuition a little bit. In the first case, $T_1(n)$ is twice $T_1(n-1)$, plus a bit more. So as you calculate $T_1(1)$, $T_1(2)$, $T_1(3)$, and so on, each time the value is more than doubled. If you take $T_1(1000)$, that is more than $T_1(1)$ doubled 999 times, more than $2^{999}$.
Basically, anything that takes previous values only a fixed distance apart, and at least multiplies by a constant > 1, you have exponential growth.
In the second case, it's $T_2(2)$, $T_2(4)$, $T_2(8)$, $T_2(16)$ and so on where $T_2$ doubles. You have to double n to double $T_2(n)$. That by itself is just linear. You add $n^2$, so you get at least $O (n^2)$, but probably not much more. If doubling n more than doubles n, then you may have more growth. Try to find a formula yourself for the case $T(n) = 3T(n/2)$ - it's n raised to some power, so find which one.
Basically, if multiplying n by one constant > 1 multiplies T(n) by another constant > 1, you get polynomial growth - depending on the constants.
