Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.1k views
in Technique[技术] by (71.8m points)

algorithm - How to solve this recurrence relation: T(n) = 4*T(sqrt(n)) + n

I know how to solve the recurrence relations using Master Method. Also I'm aware of how to solve the recurrences below:

T(n) = sqrt(n)*T(sqrt(n)) + n

T(n) = 2*T(sqrt(n)) + lg(n)

In the above two recurrences there is same amount of work at each level of the recursion tree. And there are a total of log log n levels in the recursion tree.

I'm having trouble in solving this one: T(n) = 4*T(sqrt(n)) + n

EDIT: Here n is a power of 2

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

Suppose that n = 2^k. We have T(2^k) = 4*T(2^(k/2)) + 2^k. Let S(k) = T(2^k). We have S(k) = 4S(k/2) + 2^k. By using Mater Theorem, we get S(k) = O(2^k). Since S(k) = O(2^k) and S(k) = T(2^k), T(2^k) = O(2^k) which implies T(n) = O(n).


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...