3 votes 3 votes What will be the time complexity for the following recurrence relation? $T(n) = 8\sqrt{n} T(\sqrt{n})+(log n)^{2}$ According to me it is $\Theta (n(logn)^{3})$ . Please confirm. Algorithms time-complexity recurrence-relation master-theorem + – Ashish Sharma 3 asked Jun 16, 2017 Ashish Sharma 3 1.8k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 votes Correct me if i am wrong Arnab Bhadra answered Jun 16, 2017 Arnab Bhadra comment Share Follow See all 6 Comments See all 6 6 Comments reply Ashish Sharma 3 commented Jun 17, 2017 reply Follow Share Thanks for the answer. I am having a little difficulty in understanding. Please have a look at my answer using Master Theorem. 2 votes 2 votes gari commented Jun 21, 2017 reply Follow Share we cannot apply master's theorem here because the no of subproblems should be >=1 or (a>=1). 1 votes 1 votes jatin saini commented Jul 1, 2017 reply Follow Share when you reduce size of subproblem by log in s function why you have not taken log of m^2. it should be ,P(m)=8P(m/2)+2logm/m 1 votes 1 votes Yogeshwar Misal 6 commented Jul 18, 2017 reply Follow Share @arnab ...could you please elaborate last step ... 0 votes 0 votes Arnab Bhadra commented Jul 19, 2017 reply Follow Share n(1/2+1/4+1/8+1/8....1/2^k) < n(1/2+1/4+1/8+...) = n(0.5/0.5)= n T(n) <= 8k*n T(n) = O(n(logn)3) I hope that you have understood now 1 votes 1 votes AYUSHPURNARAWAT commented May 1, 2019 reply Follow Share @Arnab please elaborate 3rd step 0 votes 0 votes Please log in or register to add a comment.