Comparing two recurrence relations w.r.t. asymptotic growth

Question

I have two functions $T_1(n),T_2(n)$. How do I decide which is asymptotically faster?

One is given by the recurrence relation

$$ T_1(n) = \sqrt{n} T_1(\sqrt{n}) + 3 n, \quad T_1(1) = T_1(2) = 1. $$

The other is given by the recurrence relation

$$ T_2(n) = 3 T_2(n/3) + 2n \log n, \quad T_2(1) = T_2(2) = 1. $$

For the first function I guess there is $O(\sqrt{n} \cdot \sqrt{n})$ for loop, and $O(n)$ for the $c$; which becomes $O(n^2)$ in total.

For the second one, the Master's theorem is applicable, but as I assume the complexity becomes $O(n \cdot n \log n) \Leftrightarrow O(n^2 \cdot \log n) \Rightarrow O(n)$ for loop, and $O(n\log n)$ for $c$.

So if I am comparing both $O()$'s, we can in total see that

$$ O(n^2) < O(n^2 \cdot \log n) $$

Was there any mistake, or is this not how recurrence unrolling is done?

Answer 1

You can sort of get a feel of the asymptotic behavior of a recurrence by flatting out the recurrence into an equivalent problem of the form $A_k = c_1(k) A_{k-1} + c_2(k)$.

First of all, to see that $O(n^2)$ is an extremely loose bound, notice how $T_1(16)$ expands out: \begin{align*} T_1(16) &= 4 T_1(4) + 3 \cdot 16 \\ &= 4 (2 T_1(2) + 3 \cdot 4) + 3 \cdot 16 \\ &= 8 + 2 \times (3 \cdot 16) \end{align*} Similarly, you'll find that $T_1(256)$ expands out to \begin{align*} T_1(256) &= 16 T_1(16) + 3 \cdot 256 \\ &= 16 (8 + 2 \times (3 \cdot 16)) + 3 \cdot 256 \\ &= \frac{256}{2} + 3 \times (3 \cdot 256) \end{align*} This strongly suggests that $T_1(2^{2^k}) = 2^{2^{k-1}} + 3k 2^{2^k}$, or $T_1(n) \approx \frac{n}{2} + 3 n\log_2 \log_2 n$. We can show this by first relaxing the domain of the function to those of the form $2^{2^k}$. Since $\sqrt{2^{2^k}} = 2^{2^{k-1}}$, we have $$ T_1(2^{2^k}) = 2^{2^{k-1}} T_1(2^{2^{k-1}}) + 3 \cdot 2^{2^k} $$ Let $A_k = T_1(2^{2^k})$, then \begin{align*} A_k &= 2^{2^{k-1}} A_{k-1} + 3 \cdot 2^{2^{k}} \\ &= 3 \cdot 2^{2^{k}} + 2^{2^{k-1}}(3 \cdot 2^{2^{k - 1}} + 2^{2^{k - 2}}A_{k-2}) \\ & \cdots \\ &= 2^{2^{k - 1}}A_{0} + 3 \cdot 2^{2^{k}} + 3 \cdot 2^{2^{k}} + \stackrel{k}{\dots} + 3 \cdot 2^{2^{k}} \end{align*}

which shows that when $n = 2^{2^k}$, then $T_1(n) = \Theta(n\log\log n)$. Suppose we now open $T_1(n)$ over the whole real domain (that is, we relax the domain restriction imposed previously), then it should be easy to show that if $T_1(x) = 1$ whenever $x \in [1, 2]$, then $T_1(n) = \frac{n}{2} + 3n \log_2\log_2 n$ extends uniformly. (Proof: Use the same derivation above, but for some other $p \in [1, 2]$, do the case analysis on $p^{2^k}$ instead)

Therefore, we have $T_1(n) = \Theta(n \log\log n)$ and $T_2(n) = \Theta(n^2 \log n)$. Asymptotically, $T_2$ still dominates $T_1$.