Intuition behind recurrences with growth O(n log n) vs O(n²)

Question

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?

Answer 1

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