2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What does "better" mean? It probably doesn't make any actual difference to an answer but one number isn't better than another; it's just bigger or smaller. $\endgroup$ – David Richerby Feb 14 '17 at 19:20
  • $\begingroup$ @DavidRicherby sorry, I should have used the word faster $\endgroup$ – user3650664 Feb 14 '17 at 19:25
  • 1
    $\begingroup$ No, one number isn't faster than another, either. $T_1$ and $T_2$ are just mathematical functions: they don't have speeds or numbers of operations or anything of that sort. $\endgroup$ – David Richerby Feb 14 '17 at 19:27
3
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ Actually, $T_2(n) = 2 n^2$. $\endgroup$ – gnasher729 Feb 16 '17 at 17:34
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.