search
Log In
3 votes
687 views
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.
in Algorithms 687 views

1 Answer

3 votes

Correct me if i am wrong

2

Thanks for the answer. I am having a little difficulty in understanding. Please have a look at my answer using Master Theorem.

1
we cannot apply master's theorem here because the no of subproblems should be >=1 or (a>=1).
1

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

0
@arnab ...could you please elaborate last step ...
1

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

0
@Arnab please elaborate 3rd step

Related questions

0 votes
1 answer
1
421 views
What is the time complexity of the following recurrence relation and step to derive the same $T(n) = T(\sqrt{n}) + log(logn)$
asked Jan 20, 2019 in Algorithms VikramRB 421 views
3 votes
1 answer
2
0 votes
0 answers
3
431 views
T (n) = T (n/2) + 2n Using Master's Method What is the Complexity Of This Recurrence Relation? Or Using AnyOther Method?
asked Aug 20, 2018 in Algorithms pradeepchaudhary 431 views
0 votes
1 answer
4
405 views
T(n) = T(n/4) + T(3n/4) + n How to solve these type of problems? Can I solve this using master theorm by considering X = T(3N/4) +N THEN T(N) = T(N/4) +X CAN WE SOLVE LIKE THIS? PLEASE HELP
asked Jan 4, 2019 in Algorithms Mayankprakash 405 views
...