search
Log In
3 votes
3.4k views

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 3.4k views
1
it should be nloglogn .
0
Which method you used to solve this?
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'.
1

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

 

0
i have used substitution method its complex a bit but u can get it easily.
0
if anyone ned that method? say, i will post that.
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.
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(2n), theta(n), theta(n2), theta(n3), theta(n4), and the option which we are supposed to mark is incorrect.

0

this may help

 

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

@gmrishikumar

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

watch this

https://gateoverflow.in/249658/recurrence-relation-mit 

0

@Gate Fever The solution is nicely done.

2 Answers

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.

selected by
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?
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.
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
Hi goxul.

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

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

@Shaik Masthan

i didnt get this part

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

1
$\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$
4 votes

Refer this is an easy way.

Related questions

4 votes
2 answers
1
8 votes
1 answer
2
4k views
How to solve above recurrence relation (With substitution method)??
asked Jan 8, 2018 in Algorithms anoop yadav 2 4k views
2 votes
4 answers
3
2.1k views
I've been struggling to come to exact solution for this. Master's theorem is not applicable and likely way to get to answer is Recursion tree. Which is giving me Theta(n) as an answer. Steps : => 1) T(n) = 2T(n/4) + √3 2) Emerging Pattern => (1/2^k) * n 3) Considering ... + n/4 + ..... = n/2 Which is incorrect , Answer given is ( √n log n ) , would appreciate if someone could shed light how so ?
asked Oct 11, 2016 in Algorithms vishal8492 2.1k views
4 votes
2 answers
4
...