Determining order class of $T(n) = n\cdot T(\frac{n}{2}) + 1$ with $T(1) = 1$

Question

Solve the following equation of recurrence, specifying the upper asymptotic limit:

$\left\{\begin{matrix} T(1) = 1 \\ T(n) = n\cdot T(\frac{n}{2}) + 1 \end{matrix}\right.$

I'm trying the iterated method:

$T(\frac{n}{2}) = \frac{n}{2} \cdot T(\frac{n}{2^2}) + 1 \\ T(\frac{n}{2^2}) = \frac{n}{2^2} \cdot T(\frac{n}{2^3}) + 1 \\ T(\frac{n}{2^3}) = \frac{n}{2^3} \cdot T(\frac{n}{2^4}) + 1 \\ ...$

$\Rightarrow$

$T(n) = n \cdot \{ \frac{n}{2} \cdot [ \frac{n}{2^2} \cdot ( \frac{n}{2^3} \cdot T(\frac{n}{2^4})+1)+1] +1\}+1 \\ ...\\ = \frac{n^4}{2^6}\cdot T(\frac{n}{2^4})+\frac{n^3}{2^3}+\frac{n^2}{2}+n+1$

And then I'm stuck. I don't see any repetitive pattern. What I'm missing?

Answer 1

Let $n=2^k$, then \begin{align} T(2^k) = 2^k\cdot T(2^{k-1}) + 1&\implies T(2^k) = 2^k\cdot 2^{k-1}\cdot T(2^{k-2}) + 2^k + 1\\ &\implies T(2^k) = 2^{k(k+1)/2}\cdot T(2^{k-k}) + \mathcal{O}(2^{k(k+1)/2})\\ &\implies T(2^k) = 2^{k(k+1)/2}+ \mathcal{O}(2^{k(k+1)/2})\\ &\implies T(n) =\mathcal{O}(n^{(\log_2n+1)/2})\\ \end{align}

Answer 2

It looks like you can show $T(n)=1/2+\sum_{i=0}^\infty \frac{n^i}{2^{i!}}$ by induction.

I don't know if you can find a closed-form expression for this, but you can bound it (for example) by $T(n)\leq 1/2+\sum_{i=0}^\infty \frac{n^i}{i!^2}\leq\sum_{i=0}^\infty \frac{n^i}{i!}=e^n$

Answer 3

The most significant "repetitive pattern" I see in

$$ \fbox{ $\frac{n^4}{2^6}\cdot T(\frac{n}{2^4})$ }+ \fbox{$\frac{n^3}{2^3}+\frac{n^2}{2}+n+1$}$$

is that the second box seems asymptotically insignificant in comparison to the first box. This suggests the following path to solving the problem:

• Find an asymptotic description of that first term
• Prove that $T$ actually satisfies the claimed description

Another way to formulate this path is to first find the asymptotic behavior of the recurrence

$$ \left\{\begin{matrix} S(1) = 1 \\ S(n) = n\cdot S(\frac{n}{2}) \end{matrix}\right.$$

and then prove that $S$ and $T$ both have the same asymptotic behavior.