edited by
11,398 views
4 votes
4 votes

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

 

Given solution is O(log log n). But my solution is O(n log log n).

'wolframalpha'' shows the answer same as mine. You can find the solution here.

 

Can anyone confirm the solution and provide an explantion?

edited by

2 Answers

Best answer
4 votes
4 votes
Given, $T(n) = \sqrt{n} T(n) + n$.

After the first substitution,we notice that:

$T(n) = \sqrt{n}[n^{1/4} T(n^{1/4}) + \sqrt{n}] + n \implies T(n) = \sqrt{n}[n^{1/4} T(n^{1/4})] + 2n $.

Continuing this series, after $k$ substitutions, we get:

$T(n) = n^{\sum_{i=1}^{k}\frac{1}{2^i}}T(n^{1/2^{k}}) + kn$.

Assuming base case as two, we'll get $k = \log \log n$.

After this, it's pretty much only calculations. Let me know if you don't get it, I'll type it out.
selected by

Related questions

0 votes
0 votes
1 answer
1
5 votes
5 votes
2 answers
2
anoop yadav 2 asked Jan 7, 2018
5,524 views
How to solve above recurrence relation?$T(n) = \sqrt{2} T(n/2) + \sqrt{n}$
0 votes
0 votes
1 answer
3
lucasbbs asked Feb 28, 2022
6,573 views
How do I apply the master theorem in the above recurrence? Please give details about which case and on hiow to solve the asymptotic analysis...
4 votes
4 votes
1 answer
4
Sanjay Sharma asked May 26, 2016
18,585 views
the solution of recurrence relationT(n)=2T(floor(sqrt(n))+log n