How to solve the recurrence equation
1.T(n)=T(n/2)+T(n/4)+\Theta(n)
2.T(1)=1
Use Big-Theta notation to give the result
+2
A:
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
Dewfy
2010-10-11 14:50:14
Yes, I know that using this series will prove T(n)=O(n),but I've no idea how to prove that T(n)=\Omega(n).
cnhk
2010-10-11 14:52:29
@cnhk: T(n) = blah + Theta(n). Is that not enough to show T(n) = Omega(n)?
Moron
2010-10-11 18:34:14
@Moron eh, What an easy solution! Thanks.
cnhk
2010-10-12 06:58:53
@cnhk no, its not. consider two cases only one of them is solved by your solution. blah works in n^2 and blah works in constant time.
none
2010-10-12 12:05:23
@none: What are you talking about?
Moron
2010-10-12 14:21:09
the question reqires that the answer will be in big theta. if you know that there is a part of it that is theta, that alone will not provide you with a good omega. maybe a loose omega. when theoretic, you are suppose to give perfect answer, and know how tight is your Omega(n) is tight. that is why its not enough to be a good result.
none
2010-10-12 16:31:17
@none: You are making no sense! What is all this talk about 'loose' and 'tight'? If T(n) = O(n) and T(n) = Omega(n), then by definition, T(n) = Theta(n). It is trivial to show that T(n) = Omega(n) (which is what the previous comments were about). The hard part is showing that T(n) = O(n), which is what the answer by Dewfy provides (I suppose, I didn't stop to verify).
Moron
2010-10-12 16:42:35
+2
A:
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.
none
2010-10-11 15:09:29