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$
5
  • $\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$ Nov 4, 2016 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, 2016 at 11:43
  • $\begingroup$ The answers to This question should provide an answer to your question about $T_1$. $\endgroup$ Nov 4, 2016 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$ Nov 4, 2016 at 15:13
  • $\begingroup$ You solve the recurrence and compare the results. $\endgroup$
    – Raphael
    Nov 7, 2016 at 10:15

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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