### Kaleem_Raza_Syed's blog

By Kaleem_Raza_Syed, history, 2 months ago,

Hello! Codeforces. Today I had created a recursion relation but I am unable to solve this to find the time complexity of the algorithm.

Recursion Relation

Please help me to solve this.

• +3

 » 2 months ago, # |   0 Here is a similar recursion relation : https://www.quora.com/What-is-time-complexity-for-T-n-%E2%88%9An-T-%E2%88%9An-+-%E2%88%9An Solve yours by the same method
 » 2 months ago, # | ← Rev. 3 →   +28 Sorry in advance, I don't know how to use latex :(T(n) = sqrt(n) * T(sqrt(n)) + n * log(sqrt(n))T(n) = sqrt(n) * T(sqrt(n)) + n * log(n) / 2n = 2^kT(2^k) = sqrt(2^k) * T(sqrt(2^k)) + 2^k * log(2^k) / 2T(2^k) = 2^(k / 2) * T(2^(k / 2)) + 2^(k-1) * kdivide both sides by 2^kT(2^k) / 2^k = T(2^(k / 2)) / 2^(k / 2) + k / 2let y(k) = T(2^k) / 2^ky(k) = y(k / 2) + k / 2y(k) = kT(2^k) / 2^k = y(k)T(2^k) = 2^k * y(k)T(2^k) = 2^k * kT(n) = n * log(n)
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 y(k) = y(k / 2) + k / 2y(k) = kCan you explain how you got this?
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 It's obvious that y(k) = k / 2 + k / 4 + k / 8 + k / 16 + ... Using formula for sum of geometric series, you can get that y(k) = k
•  » » » » 2 months ago, # ^ |   0 Oh! yeah. Thanks for the solving this.