The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
461 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 by (331 points) | 461 views

1 Answer

+3 votes

Correct me if i am wrong

by Active (4.7k points)
+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

+6 votes
1 answer
7
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
49,831 questions
54,735 answers
189,349 comments
80,096 users