The Gateway to Computer Science Excellence
+4 votes
266 views

$T(n)=\sqrt{n} T(\sqrt{n})+100n$

Please solve this.

in Algorithms by Boss (17k points) | 266 views
0
is ans  $\Theta (100n)=\Theta (n)$?

then simply take $n=2^{m}$
0
i didn't get you sretha

3 Answers

+12 votes
Best answer

ans is O(n log logn)

 

by Boss (13.7k points)
selected by
0
but @Magma
is master theorem applicable here?
See this https://gateoverflow.in/11211/how-to-find-the-complexity-of-t-n-t-sqrt-n-1
+1
thanks a lot. How did this substitution came to ur mind??
0
yes  ,mam masters theorem is applicable here

This is a special type of recurrence relation
+2

sushmita   I have  done this questions  earlier  on and note it down in my copy :p 

because this is a special type of recurrence relation which is doing in this manner

+6 votes

This may suffice.

by Junior (831 points)
0
thanks great answer indeed
0 votes
it will be O(n^loglogn)
by (139 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,650 questions
56,238 answers
194,266 comments
95,873 users