algorithm - Solve recurrence 2T(n^1/2 )+c assuming T(1) and c are constants -
got 'essential algorithms' exam doing bit of revision. came across question , unsure whether answer right.
this imgur link has question , working.
http://imgur.com/sfkurqo
could verify whether right / ive went wrong?
i can't follow handwriting point out went wrong, here's how it:
t(n) = 2t(n^(1/2)) + c = 2(2t(n^(1/4)) + c) = ... = 2^kt(n^(1/2^k)) + 2^(k - 1)c
so need find smallest k
such that:
n^(1/2^k) = 1 (considering integer part)
we can apply logarithm expression:
1/(2^k) log n = 0 (remember we're considering integer parts) => 2^k >= log n | apply logarithm again => k log 2 >= log log n => k = o(log log n) because log 2 constant
so have:
2^o(log log n)t(1) + 2^o(log log n - 1)c = o(2^log log n) = o(log n)
i see got o(sqrt(n))
, isn't wrong either, because log n < sqrt n
, if log n
upper bound, sqrt n
. it's not tight bound.
Comments
Post a Comment