1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – David Richerby Nov 4 '16 at 10:49
  • $\begingroup$ 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? $\endgroup$ – waplet Nov 4 '16 at 11:43
  • $\begingroup$ The answers to This question should provide an answer to your question about $T_1$. $\endgroup$ – Rick Decker Nov 4 '16 at 13:42
  • 1
    $\begingroup$ 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?" $\endgroup$ – Rick Decker Nov 4 '16 at 15:13
  • $\begingroup$ You solve the recurrence and compare the results. $\endgroup$ – Raphael Nov 7 '16 at 10:15
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Btw, the Master's theorem gives - $T_2(n) = \Theta(n\log^2 n)$ $\endgroup$ – waplet Nov 8 '16 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.