Kaleem_Raza_Syed's blog

Can you solve this?
By Kaleem_Raza_Syed, history, 2 months ago, In English

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.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 months ago, # |
← Rev. 3   Vote: I like it +28 Vote: I do not like it

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) / 2

n = 2^k

T(2^k) = sqrt(2^k) * T(sqrt(2^k)) + 2^k * log(2^k) / 2

T(2^k) = 2^(k / 2) * T(2^(k / 2)) + 2^(k-1) * k

divide both sides by 2^k

T(2^k) / 2^k = T(2^(k / 2)) / 2^(k / 2) + k / 2

let y(k) = T(2^k) / 2^k

y(k) = y(k / 2) + k / 2

y(k) = k

T(2^k) / 2^k = y(k)

T(2^k) = 2^k * y(k)

T(2^k) = 2^k * k

T(n) = n * log(n)

→ Reply