Skip to content

p6.md

Latest commit

 

History

History
16 lines (13 loc) · 1.27 KB

p6.md

File metadata and controls

16 lines (13 loc) · 1.27 KB

Problem

Solve the recurrence T(n)=2T(sqrt(n))+1 by making a change of variables. Your solution should be asymptotically tight. Do not worry about whether values are integral.

Solution

T(n)=2T(sqrt(n))+1
let m=log(n), n=2^m
⇒T(2^m)=2T(2^(m/2))+1
let S(m)=T(2^m)
⇒S(m)=2S(m/2)+1
by master theorem: a=2, b=2, f(n)=1
S(m)=m^(log2)=m
⇒S(m)=\Theta(m)
⇒T(2^m)=\Theta(m)
⇒T(n)=\Theta(logn)