T(n) = T(n - √n) + T(√n) + n
Post your answers/solutions in the comments. We were asked this in the final exam in CSE-548 (Analysis Of Algorithms taught by Dr. Michael Bender).
Subscribe to:
Post Comments (Atom)
Just something whacky to get you thinking. At least it got me pulling apart my hair, and now, I'm half bald.
7 comments:
Can I answer? :)
@Gaurav only if you have a complete derivation, which isn't empirical.
n^(3/2) ?
@Aniruddha I want to know how you got that answer.
Not a very tight upper bound. The depth of the tree should be n^1/2 from what I see. I could be wrong though. Is it the right answer?
@Aniruddha You aren't subtracting sqrt(n) at every step, are you? It's more like subtracting sqrt(n), sqrt(n-sqrt(n)), sqrt(sqrt(n-sqrt(n))-sqrt(sqrt(n-sqrt(n)))), etc...
seems like O(nloglogn)
Post a Comment