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

enter image description here

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

Popular posts from this blog

android - MPAndroidChart - How to add Annotations or images to the chart -

javascript - Add class to another page attribute using URL id - Jquery -

firefox - Where is 'webgl.osmesalib' parameter? -