5 votes 5 votes $T(n)=\sqrt{n} T(\sqrt{n})+100n$ Please solve this. Algorithms recurrence-relation algorithms time-complexity discrete-mathematics + – sushmita asked Oct 4, 2018 recategorized Jul 6, 2022 by Lakshman Bhaiya sushmita 2.1k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply srestha commented Oct 4, 2018 reply Follow Share is ans $\Theta (100n)=\Theta (n)$? then simply take $n=2^{m}$ 0 votes 0 votes sushmita commented Oct 4, 2018 reply Follow Share i didn't get you sretha 0 votes 0 votes srestha commented Oct 4, 2018 reply Follow Share https://gateoverflow.in/11211/how-to-find-the-complexity-of-t-n-t-sqrt-n-1 0 votes 0 votes Please log in or register to add a comment.
Best answer 19 votes 19 votes ans is O(n log logn) Magma answered Oct 4, 2018 selected Oct 4, 2018 by sushmita Magma comment Share Follow See all 4 Comments See all 4 4 Comments reply srestha commented Oct 4, 2018 reply Follow Share 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 0 votes 0 votes sushmita commented Oct 4, 2018 reply Follow Share thanks a lot. How did this substitution came to ur mind?? 1 votes 1 votes Magma commented Oct 4, 2018 reply Follow Share yes ,mam masters theorem is applicable here This is a special type of recurrence relation 0 votes 0 votes Magma commented Oct 4, 2018 reply Follow Share 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 3 votes 3 votes Please log in or register to add a comment.
7 votes 7 votes This may suffice. Shaijal Tripathi answered Oct 4, 2018 Shaijal Tripathi comment Share Follow See 1 comment See all 1 1 comment reply sushmita commented Oct 4, 2018 reply Follow Share thanks great answer indeed 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes it will be O(n^loglogn) abhi19961 answered Oct 4, 2018 abhi19961 comment Share Follow See all 0 reply Please log in or register to add a comment.