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)

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

#### 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)}$.