How to solve the recurrence equation T(n)=T(n/2)+T(n/4)+\Theta(n)?

How to solve the recurrence equa开发者_如何学JAVAtion

1.T(n)=T(n/2)+T(n/4)+\Theta(n)

2.T(1)=1

Use Big-Theta notation to give the result

---

well then we look at this question carfuley we can analys it.

lets start with examples, as we explore them we could reach better understanding on how to solve them(the other problem is how to represent the data we have, but that is a computer sientenst to know how to represent data to be readable). (hint, anything below 1 is rounder to 1

T(1) = 1

T(2) = 1 + 1

T(3) = T(1.5) + 1

T(4) = T(2) + 1

T(5) = T(2.5) + T(1.25)

T(2.5) = T(1.25) + 1

T(6) = T(3) + T(1.3333)

now if we do rounds we can get to understanding that whats betwee 1 and 2 can take upper bound of 2 or lower bound of 1.

as a hint ill say if you prove that when you take all upper bounds and get the teta you want, and if you take all the lower bound teta you want, then you prove that its bounded by the same teta.

now lets examine the upper teta

T(1) = 1

T(2) = 1 + 1

T(3) = T(2) + 1 = (1 + 1) +1

T(4) = T(2) + 1 = (1 + 1) +1

T(5) = T(3) + T(2) = (1 + 1 + 1) + (1 + 1)

T(6) = T(3) + T(2) = (1 + 1 + 1) + (1 + 1)

do you see its linear?

can you come out of a furmula from this?

this is how you approach this kind of questions.

good luck,

don't forget the lower bound analysis.

---

I don't want to give you direct answer, but my hint: look for Mathematical series of form:

1/2 + 1/4 + ... + 1/2^n