math - Troublesome recurrence equation: T(n) = 2*T(ceil((sqrt(n)))+1 -

math - Troublesome recurrence equation: T(n) = 2*T(ceil((sqrt(n)))+1 -

i have encountered recurrence problem:

t(n) = 2*t(ceil((sqrt(n)))+1

t(1)=1;

i unable see function terminate @ when draw recurrence tree. general node form in tree (n1/2i) becomes 1 when 1/2i becomes 0. means should tend infinity.

you're right if sqrt ceiling of square root, you'll never reach 1 repeatedly applying square roots. i'm going assume meant utilize floor, means indeed nail 1 recurrence unwinds.

in case, recurrence more properly

t(1) = 1

t(n) = 2t(⌊√n⌋) + 1

a standard technique solving recurrences involve square roots create substitution. let's define new value k such n = 2k. notice √n = (2k)1/2 = 2k/2. in other words, taking square root of n equivalent halving value of k. because of this, can convert above recurrence, involves square roots, new recurrence more closely match form used master theorem , other recurrence-solving techniques. specifically, let's define s(k) = t(2k). recurrence

s(0) = 1

s(k) = 2s(⌊k / 2⌋) + 1

it's lot easier see how solve recurrence. either recognizing recurrence elsewhere or using master theorem, s(k) = θ(k). now, wanted solve t(n), can utilize fact s(k) = t(2k) = t(n). since s(k) = θ(k), see t(n) = θ(k). since chose k such 2k = n, means k = lg n. therefore, t(n) = θ(log n), recurrence works out θ(log n).

hope helps!

math recurrence recurrence-relation