Simplifying Recurrence Relation c(n) = c(n/2) + n^2

Question

I'm really confused on simplifying this recurrence relation: c(n) = c(n/2) + n^2.

So I first got:

c(n/2) = c(n/4) + n^2 so c(n) = c(n/4) + n^2 + n^2 c(n) = c(n/4) + 2n^2

c(n/4) = c(n/8) + n^2 so c(n) = c(n/8) + 3n^2

I do sort of notice a pattern though:

2 raised to the power of whatever coefficient is in front of "n^2" gives the denominator of what n is over.

I'm not sure if that would help.

I just don't understand how I would simplify this recurrence relation and then find the theta notation of it.

EDIT: Actually I just worked it out again and I got c(n) = c(n/n) + n^2*lgn.

I think that is correct, but I'm not sure. Also, how would I find the theta notation of that? Is it just theta(n^2lgn)?

Answer 1

Firstly, make sure to substitute n/2 everywhere n appears in the original recurrence relation when placing c(n/2) on the lhs.

i.e.

c(n/2) = c(n/4) + (n/2)^2

Your intuition is correct, in that it is a very important part of the problem. How many times can you divide n by 2 before we reach 1?

Let's take 8 for an example

8/2 = 4
4/2 = 2
2/2 = 1

You see it's 3, which as it turns out is log(8)

In order to prove the theta notation, it might be helpful to check out the master theorem. This is a very useful tool for proving complexity of a recurrence relation.

Using the master theorem case 3, we can see

a = 1
b = 2
logb(a) = 0
c = 2
n^2 = Omega(n^2)
k = 9/10
(n/2)^2 < k*n^2
c(n) = Theta(n^2)

The intuition as to why the answer is Theta(n^2) is that you have n^2 + (n^2)/4 + (n^2)/16 + ... + (n^2)/2^(2n), which won't give us logn n^2s, but instead increasingly smaller n^2s