The Gateway to Computer Science Excellence
+1 vote

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?

in Algorithms by Active (2.1k points) | 803 views
it should be nloglogn .
Which method you used to solve this?
@`JEET I tried solving it but couldn't. That's why I needed help.

But just by looking at it I thought it would be O(n log log n). I also checked the recursive relation on 'wolframalpha'.

We can assume the solution and then prove it by induction as follows:


i have used substitution method its complex a bit but u can get it easily.
if anyone ned that method? say, i will post that.
@arvin Please post the solution.

I am looking at all the ways to solve the problem and learn when do you stop simplifying the problem.

@goxul But what if I don't have a solution.

This question was a part of a match the following question and had 6 options.

Yeah, the problem with induction is that you need to make a guess and then prove that your solution is correct. So if you have a lot of options, the better way would be to go with substitution. Let me try with that once.

The options given are theta(log log n), theta(2n), theta(n), theta(n2), theta(n3), theta(n4), and the option which we are supposed to mark is incorrect.


this may help


cant we do it using master theorem??
I dont think you can do it that way.


after i commented here, i saw similar question which was beautifully solved using master theorem;

watch this 


@Gate Fever The solution is nicely done.

2 Answers

+1 vote
Best answer
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.
by Loyal (6.7k points)
selected by
@goxul I had troubles solving this. But now I got this.

But can you tell me how long should I continue expansion and which terms should I ignore?
Oh, that part.

We keep on expanding till we reach the base case - because for the base case, we can plug in the value directly. In this case, I've assumed that the base case is $T(2) = 1$. We will reach this point when $n^{1/2^{k}}$ becomes equal to two. For that case, we'll get $k = \log \log n$. Once we get that, notice $T(n^{1/2^{k}})$ becomes one, as $T(2) = 1$.

I hope this makes sense.

Got it.

Thanks a lot for the help.

If you have time, take look at this question. Here is where I don't know when to approximate and when to ignore some terms.

Hi goxul.

Can you please post the calculation of k. Just want to know how approximation is done.
Is the base condition correct?

Putting T(2) in LHS and RHS in equation 1 should give the right value?
@'JEET $n^{1/2^k} = 2 \implies \frac{1}{2^k} \log n = 1 \implies \log n = 2^k \implies k = \log \log n$

@Shaik Masthan

i didnt get this part

$\frac{n}{n^{\frac{1}{2^{k}}}} ==> n / 2 $

$\frac{1}{2^k}$ = ${(2^k)}^{-1}$ ===> substitute ${(2^k)}$ = log n

then $\frac{1}{2^k} = {(log_2n)}^{-1} = log_n2$

$n^{\frac{1}{2^k}} =n^{log_n2} = 2^{log_nn} = 2$
+3 votes

Refer this is an easy way.

by (231 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,312 answers
105,031 users