# Recurrences

Solve the recurrence T(n) = 2T(sqrt(n)) + 1 by making change of variables. The solution should be asymptotically tight.

2. Use a recursive tree to give an asymptotically tight solution to the recurrence T(n) = T(n-a) + T(a) + cn, where n > = 1 and c > 0 are constants.

#### Solution Preview

Question 1

----------

T(n) = 2T(sqrt(n)) + 1 ----- (1)

If you let n = m^2, then this is

T(m^2) = 2 T(m) + 1 ----- (2)

This is reminiscent of the law of logarithms

log (m^2) = 2 log m ----- (3)

to some base b.

However, there is a bugging "+ 1" constant term to deal with.

Let T(m) = log m + k ----- (4)

where k is a constant to be found.

Substituting into (2), we get

log m^2 + k = 2 (log m + k) + 1

2 log m + k = 2 log m + 2k + 1

canceling and solving, we get

k = -1

Therefore we guess T(m) to be of the form

T(m) = log m - 1

Since m is just a dummy variable, we can also write

T(n) = log n - 1

To verify asymptotic tightness:-

Suppose T(m) > T(b^2) [log m - 1] for all m >_ b

Multiply both sides by 2 and add 1, we get

2 T(m) + 1 > T(b^2) [2 (log m - 1) + 1]

T(m^2) > T(b^2) [2 log m - 1]

In particular,

T(b^2) > T(b^2) [2 log b - 1]

1 > 2 log b - 1

1 > log b

This cannot hold for all b. Therefore

there must exist some b and c2 such that

for all m >_ b

T(m) _< c2 (log m - 1) (c2 = T(b^2))

[The above inequalities can be tweaked to give a c1 so that

c1 (log m - 1) _< T(m).]

[The ...

#### Solution Summary

This is two problems regarding recurrences.