CODEWITHSUNDEEP
algorithmtime-complexitybig-orecurrence
Sara
Sara

Reputation: 1

How to simplify the summation of a recurrence relation

After solving the recurrence relation T(n) = 3T(n/3) + nlogn

I get following equation: T(n)=3kT(n/3k)+ nlogn + nlog(n/3) + nlog(n/3^2) …nlog(n/3^k)

How can I simplify the summation and how to know the asymptotic function?

Upvotes: 0

Views: 105

Answers (1)

user55924
user55924

Reputation: 219

log a + log b = log(a*b), so something like
T(n) = 3kT(n/3k) + n^k*logn(\Pi_k(n/(3^k)))

product of 1/(3^k) (\Pi_k(1/(3^k))) is 3^(-1/2k(k+1)) so it simplifies the logs become the single term n*log{3^(-1/2k(k+1)) * n^(k+1)}

that takes care of the simplification i gues..

Upvotes: 0

Related Questions