1
$\begingroup$

$T(n) = T(n-2)+T(n-3)+2T(n/3)$ and $T(n)=1$ for $n<4$. I tried to compute the complexity of $T(n) = T(n-2)+T(n-3)+2T(n/3)$ using the recursion tree but it's not clear enough for me to make a guess and demonstrate it by induction? also, it should be computed given both upper and lower bound.

$\endgroup$
  • 4
    $\begingroup$ Note that you're not computing the complexity of anything. You're solving a recurrence relation to determine a function. That function could be used to measure anything at all, not necessarily the running time of an algorithm. This is a bit like saying you're trying to "compute the cost of 4.50+3.99": actually, you're just trying to add two numbers: 8.49 doesn't cost anything; it is the cost, assuming the numbers represent prices. $\endgroup$ – David Richerby Nov 28 '18 at 19:00
  • 4
    $\begingroup$ Possible duplicate of Solving or approximating recurrence relations for sequences of numbers $\endgroup$ – David Richerby Nov 28 '18 at 19:00
  • $\begingroup$ I can't find the complexity using the methods given in the links. $\endgroup$ – Sydney.Ka Nov 28 '18 at 22:09
  • $\begingroup$ Use the techniques used for solving the Fibonacci recurrence. $\endgroup$ – Raphael Nov 28 '18 at 22:50
  • $\begingroup$ High reputation-ers, before voting for duplicate, could you check how you will find and prove an asymptotic by Θ for this function? Once you are done, will you believe it is a duplicate to that reference question/answers? When I checked every answer there, I could not solve this question initially. I had to find something new. By the way, I believe that I am not bad at recurrence relations. If I cannot find the reference question good enough for this question, I doubt how many others can, unless only a loose big $O$ is sought. $\endgroup$ – John L. Nov 29 '18 at 5:49
1
$\begingroup$

Summary: $T(n) = \Theta(\alpha^n)$, where $\alpha=\sqrt[3]{\frac{9+\sqrt{69}}{18}}+\sqrt[3]{\frac{9-\sqrt{69}}{18}}\approx 1.324718$.

Find $\alpha$

Let $\alpha$ be the unique positive root of $x^3=x+1$.

We can solve the equation manually by the standard method, letting $x=w+\frac 1{3w}$ and solving $w$. If we trust the online calculators or you can use some software package such as MatLab, Maple, Wolfram Alpha or Python numpy.root, you can find all the exact roots or the approximate roots. In fact, since all we need is a positive root, we could also cheat a bit by just verifying directly the following quantity is a root. $$\alpha=\sqrt[3]{\frac{9+\sqrt{69}}{18}}+\sqrt[3]{\frac{9-\sqrt{69}}{18}}\approx 1.324718$$

Reference function $S$

Let $S(n)= S(n-2)+S(n-3)$ and $S(n)=1$ for $n<4$.

Claim: $\frac{\alpha^n}{3}<S(n)<\alpha^n$ for all $n\ge1$.

Proof by mathematical induction on $n$.

  • The base case when $1\le n\le3$ is easy since $1<\alpha$ and $\alpha^3<3$.
  • Since $\alpha^3=\alpha+1$, the induction step is easy. Assume the claim is true when $n\le k-1$ for some $k\ge3$. Then $$S(k)=S(k-2)+S(k-3)>\frac{\alpha^{k-2}}{3}+\frac{\alpha^{k-3}}3=\frac{\alpha^k}3$$ $$S(k)=S(k-2)+S(k-3)<\alpha^{k-2}+\alpha^{k-3}=\alpha^k$$

Last Trick

Claim One: $S(n)\le T(n)$ for all $n\ge1$.

Proof: It is easy to prove by mathematical induction that $T(n)>0$ for all $n\ge1$. $S(n)\le T(n)$ follows easily by mathematical induction.

Lemma: there exists a constant $c>0$ such that for all $n\ge c$, $\alpha^{\frac{2n}3} > 3n^2$.

Proof. This is obvious since any growing exponential function grows faster than any polynomial, a well-known fact that is (almost) proved in this answer. (We can take c=72, for example.)

Claim Two: There exist a constant $d>0$ such that $T(n)<d(1-\frac1n)S(n)$ for all $n\ge1$. (That factor $1-\frac1n$ is the "last trick".)

Proof. Let $c>4$ be a constant as in the lemma. Let $d=1+2\max_{1\le n<c}(T(n))>1$. Let us prove $T(n)<d(1-\frac1n)S(n)$ by mathematical induction on $n$.

  • The base case when $n<c$. $T(n) < d/2 \le d(1-\frac1n) \le d(1-\frac1n)S(n)$.
  • Suppose the inequality is true for all $n\le k-1$, where $k\ge c$. Then

$$ \begin{aligned} T(k)=& T(k-2) + T(k-3) + 2T(k/3)\\ \lt& d(1-\frac1{k-2})S(k-2) + d(1-\frac1{k-3})S(k-3) + 2d(1-\frac1{\frac k3})\alpha^{\frac k3} \\ \lt&d(1-\frac1{k-2})(S(k-2)+S(k-3)) + 2d\alpha^{\frac k3}\\ =&d(1-\frac1{k-2})S(k) + 2d\alpha^{\frac k3}\\ =&d(1-\frac1{k})S(k) - \frac{2d}{(k-2)k}S(k)+ 2d\alpha^{\frac k3} \\ \lt&d(1-\frac1{k})S(k) - \frac{2d}{(k-2)k}\frac13\alpha^k+ 2d\alpha^{\frac k3} \\ =&d(1-\frac1{k})S(k) - \frac{2d\alpha^{\frac k3}}{3(k-2)k}(\alpha^{\frac {2k}3} - 3(k-2)k)\\ \end{aligned}$$

Since $\alpha^{\frac {2k}3} - 3(k-2)k \gt \alpha^{\frac {2k}3} - 3k^2\gt0$, we obtain $T(k) \lt d(1-\frac1{k})S(k)$.

Claim Three: $T(n)=\Theta(\alpha^n)$

Proof: This follows immediately from the two above claims since $\frac{\alpha^n}{3}<S(n)<\alpha^n$ and $d(1-\frac1n)\le d$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The last step is the most difficult one. Adding back the term $2T(n/3)$, show that T(n) = $\Theta(\alpha^n)$ $\endgroup$ – John L. Nov 29 '18 at 3:30
  • 1
    $\begingroup$ If this is a homework exercise for beginners, then Rishabh's answer might be enough for you to get a full mark on this problem. My answer might be too advance to be expected. $\endgroup$ – John L. Nov 29 '18 at 17:17
  • 1
    $\begingroup$ Since $\alpha$ appears in the sharp estimate $\Theta(\alpha^n)$, there is no way to get round it unless we just want to show, for example, $T(n)=2^{\Theta(n)}$. $\endgroup$ – John L. Nov 29 '18 at 17:24
  • 1
    $\begingroup$ You do not have to solve that equation, though. If you have learned calculus, it can be shown that equation has a unique real root, which is between 1.2 and 1.5. We can name it $\alpha$ then. $\endgroup$ – John L. Nov 29 '18 at 17:29
  • 1
    $\begingroup$ For linear recurrence such as the one for $S(n)$, you may want to study brilliant.org/wiki/linear-recurrence-relations. For this $T(n)$, which is sort of one of kind, it is more like arts and experiences, although we can make some generalizations. $\endgroup$ – John L. Nov 29 '18 at 21:47
1
$\begingroup$

You can notice that $T(n) < 3T(n-2)$. This gives you the complexity as $O(3^{n/2})$. You can also observe that $T(n) > 2T(n-3)$. This gives you the complexity as $\Omega(2^{n/3})$. Now, you can at least tell that the complexity is an exponential one.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer, but is there a way to find the complexity with the notation big theta? $\endgroup$ – Sydney.Ka Nov 28 '18 at 20:43
  • 1
    $\begingroup$ Of course there is a way. As Raphael said "Use the techniques used for solving the Fibonacci recurrence". There are matrices involved and Eigenvalues. If you don't know what an Eigenvalue is, then solving this is tough. $\endgroup$ – gnasher729 Nov 29 '18 at 0:40
  • 1
    $\begingroup$ Upvoted because the result is very easy to find and explain, and useful. $\endgroup$ – gnasher729 Nov 29 '18 at 0:45
  • $\begingroup$ Thank you for your answer but I don't know how to find to use the Fibonacci method since it's much easier to find the equation to solve for the fibonacci recurrence? $\endgroup$ – Sydney.Ka Nov 29 '18 at 14:46

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.