Recursion tree and substitution method

Question

I have this exercise:

"use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n)=T(n/2)+n^2. Use a substitution method to verify your answer"

I have made this recursion tree

Where I have assumed that k -> infinity (in my book they often stop the reccurence when the input in T gets 1, but I don't think this is the case, when I don't have other informations).

I have concluded that:

When I have used the substitution method I have assumed that T(n)=O(n^2)

And then done following steps:

When n>0 and c>0 I see that following is true for some choice of c

And therefore T(n)<=cn^2

And my question is: "Is this the right way to do it? "

Answer 1

First of, as Philip said, your recursion tree is wrong. It didn't affect the complexity in the end, but you got the constants wrong.

T(n) becomes
n^2 + T(n/2) becomes
n^2 + n^2/4 + T(n/4) becomes
...
n^2(1 + 1/4 + 1/16 + ...)

Stoping at one vs stoping at infinity is mostly a matter of taste and choosing what is more convenient. In this case, I'd do the same as you did and use the infinite sum, because then we can use the geometric series formula to get a good guess that T(n) <= (4/3)n^2

---

The only thing that bothers me a bit is that your proof in the end tended towards the informal. It is very easy to get lost in informal proofs so if I had to grade your assignment, I'd be more confortable with a traditional proof by induction, like the following one:

statement to prove

We wish to prove that T(n) <= (4/3)*n^2, for n >= 1

Concrete values for c and n0 make the proof more belieavable so put them in if you can. Often you will need to run the proof once to actualy find the values and then come back and put them in, as if you had already known them in the first place :) In this case, I'm hoping my 4/3 guess from the recursion tree turns out correct.

Proof by induction:

Base case (n = 1):

T(1) = 1 

(You did not make the value of T(1) explicit, but I guess this should be in the original exercise)

T(1)  = 1
     <= 4/3
      = (4/3)*1^2
T(1) <= (4/3)*1^2

As we wanted.

Inductive case (n > 1):

(Here we assume the inductive hypothesis T(n') <= 4/3*(n')^2 for all n' < n)

We know that

T(n) = n^2 + T(n/2)

By the inductive hypothesis:

T(n) <= n^2 + (4/3)(n/2)^2

Doing some algebra:

T(n) <= n^2 + (4/3)(n/2)^2
      = n^2 + (1/3)n^2
      = (4/3)n^2
T(n) <= (4/3)*n^2

As we wanted.

---

May look boring, but now I can be sure that I got the answer right!

Answer 2

Your recursion tree is erroneous. It should look like this:

n^2
|
(n/2)^2
|
(n/4)^2
|
...
|
(n/2^k)^2

You can safely stop once T reaches 1, because you are usually counting discrete "steps", and there's no such thing as "0.34 steps".

Since you're dividing n by 2 in each iteration, k equals log2(n) here.