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

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?

• What do you mean by "$O(n^2)<O(n^2\log n)$? Note that, for example, $n^2\in O(n^2)$ and $n\in O(n^2\log n)$ but $n^2>n$ for $n>1$. Nov 4 '16 at 10:49
• I have two questions? 1. Does my assumption that first functon is faster is correct? 2. Have i made correct O's from the recurrance functions? Nov 4 '16 at 11:43
• The answers to This question should provide an answer to your question about $T_1$. Nov 4 '16 at 13:42
• Terminology: the notion of "faster" doesn't apply to functions. To be precise you should either ask "which of these functions is asymptotically smaller?" or "These are timing functions for two algorithms, which algorithm is asymptotically faster?" Nov 4 '16 at 15:13
• – Raphael
Nov 7 '16 at 10:15

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$.
• Btw, the Master's theorem gives - $T_2(n) = \Theta(n\log^2 n)$ Nov 8 '16 at 10:14