1
$\begingroup$

Been trying to get the intuition behind why two very similar recurrence relations don't follow a pattern I would expect. They are pretty well known relations:

Relation 1 -

$T(n) = 2T(\frac{n}{2}) + n$

Relation 2 -

$T(n) = 2T(\frac{n}{2}) + n^2$

When sketching out a tree for the first recurrence, the way I was taught to think that at every level of a tree, you are doing some amount of work.

Height 1 - do some O(n) of work
Height 2 - do some O(n) of work
Height log(n) - do some O(n) of work

Now In my head, If i visualize the work as a sum of all the work done, it seems like its $O(n\log(n))$ of work being done, which according to the master theorem is correct.

However, using the same intuition for the second recurrence is wrong as we know the master theorem tells us the answer is $O(n^2)$.

Any reason why the intuition seems to be correct for the first recurrence, and why it is wrong for the second?

$\endgroup$
4
$\begingroup$

What you are missing is the big O constants. In the first case, at successive heights you are doing work of $$n, 2\frac{n}{2}, 4\frac{n}{4}, \ldots = n,n,n,\ldots. $$ In the second case, at successive heights you are doing work of $$n^2,2\frac{n^2}{4}, 4\frac{n^2}{16}, \ldots = n^2,\frac{n^2}{2},\frac{n^2}{4}.$$ Since the series $1,1/2,1/4,\ldots$ converges, the total work is only $O(n^2)$.

$\endgroup$
  • $\begingroup$ Ah, so in this case, those constants are important. Very good reminder :) Thanks! $\endgroup$ – C.B. Sep 24 '14 at 15:53
  • 1
    $\begingroup$ @C.B. The specific values are not, the fact that they are squared is. $\endgroup$ – Raphael Sep 25 '14 at 5:35

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.