3 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?

0

@`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'.

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

0

@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.

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

0

@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.

0

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.

0

The options given are theta(log log n), theta(2^{n}), theta(n), theta(n^{2}), theta(n^{3}), theta(n^{4}), and the option which we are supposed to mark is incorrect.

3 votes

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.

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.

0

@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?

But can you tell me how long should I continue expansion and which terms should I ignore?

1

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.

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.

1

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.

0

Is the base condition correct?

Putting T(2) in LHS and RHS in equation 1 should give the right value?

Putting T(2) in LHS and RHS in equation 1 should give the right value?