Solving the recurrence T (n) = T (n / 2) + Θ (1) by substituting

So, I understand how to do it when the repetition looks something like this:

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

In this case, I would guess the answer would be O (nlogn) and then use induction to prove it. But for this I am thrown out by Θ (1). How would you do it? If you could do the induction steps that would be awesome.

Thank you very much!

+3


source to share


1 answer


try substituting the value recursively



T(n) = T(n/2) + Θ(1)
 = (T(n/4) + Θ(1)) + Θ(1)  = T(n/4) + Θ(1) + Θ(1)  = T(n/4) + 2*Θ(1)
 = (T(n/8) + Θ(1)) + 2*Θ(1)= T(n/8) + 3*Θ(1)
 = T(n/16) + 4*Θ(1)
 = T(n/32) + 5*Θ(1) [ T(n/2^5) + 5*Θ(1) ]
 .                                           
 .                                           
 = T(1) + log2(n)*Θ(1)
 = O(log2(n))

      

+2


source







All Articles