Share
Explore BrainMass

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.

$2.19