Explore BrainMass

Solving a recurrence

Solve the following recurrence exactly for n of the form 2^2^k.

T(2) = 1
T(n) = 2T(n^(1/2)) + log n

Express your answer as simply as possible using theta notation.
note added ** theta notation is based on big O notation

Show all work!

Solution Preview


Let n=2^2^k, then we have
T(n)=T(2^2^k)=2T(n^(1/2))+log ...

Solution Summary

This shows how to solve a recurrence using theta notation.