Cheap and Secure Web Hosting Provider : See Now

[Solved]: Running time of this recursive relation: T(n) = (n/2)T(n/2) + O(n^2)

, , No Comments
Problem Detail: 

I encountered these few recursive relations:

T(n) = (n/2)T(n/2) + O(n^2)

T(n) = T(n/2) + T(n/2-1) + ... + T(1) + O(n^2)

I do notice that these recursions can be solved faster by DP. I'm just curious as to:

  1. What's the big-O of the running time of these relations, if we follow the resursive formula
  2. How do you analysis recursive relations like these.
  3. Does the trailing term (in this case O(n^2)) matter?

Any help is much appreciated.

Asked By : Boyang

Answered By : Yuval Filmus

You can solve the first recurrence for powers of $2$. The recurrence (without the big O and with an arbitrary base case) reads $$ T(2^k) = 2^{k-1} T(2^{k-1}) + 4^k, \quad T(2^0) = 4^0. $$ Opening the recurrence, we get $$ T(2^k) = 4^k + 2^{k-1} \cdot 4^{k-1} + 2^{k-1+k-2} \cdot 4^{k-2} + \cdots + 2^{k-2+\cdots+1} 4^0. $$ Denote these by $T(2^k) = \alpha_0 + \cdots + \alpha_\ell$. We have $$ \frac{\alpha_\ell}{\alpha_{\ell-1}} = 2^{k-\ell-1}. $$ Therefore the largest term is $\alpha_{k-1} = \alpha_{k-2}$, and the rest of the terms decrease geometrically. This shows that $$ T(2^k) = \Theta(\alpha_{k-1}) = \Theta(2^{k-1+\cdots+1} 4^1) = \Theta(2^{k(k-1)/2}). $$ As you can see, the term $O(n^2)$ in the recurrence isn't important, and you will get similar result for any term $O(n^c)$.

One could guess that the general solution to the first recurrence (with $\lfloor n/2 \rfloor$ replacing $n/2$) is $T(n) \Theta(2^{\log_2 n(\log_2 n - 1)/2})$, and one could further guess that the second recurrence has the same solution (though that's a wilder guess). I'm not sure these guesses are correct. At the very least, the first recurrence should have the solution $T(n) = 2^{\Theta(\log^2 n)}$.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback