Sunday, January 08, 2012

Solve this recurrence

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).

7 comments:

Gaurav Menghani said...

Can I answer? :)

dhruv said...

@Gaurav only if you have a complete derivation, which isn't empirical.

Aniruddha said...

n^(3/2) ?

dhruv said...

@Aniruddha I want to know how you got that answer.

Aniruddha said...

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?

dhruv said...

@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...

rigelbm said...

seems like O(nloglogn)