0
$\begingroup$

I encountered the following recurrence relation in homework, for which we need to find its asymptotics: $$T\left(n\right)=T\left( \frac{n}{3} \right) + T\left( \frac{n}{6} \right) + 1$$

I observed it is possible to approach this relation with the method of Akra-Bazzi, however this method was not taught in class. Akra-Bazzi gives the result of $\theta(n^p)$ where $p$ is the unique solution to $$\frac{1}{3^p}+\frac{1}{6^p}=1$$

However, since this was not taught, I would like to ask if there's a different method to tackle this exercise, or a way to find its asymptotics more constructively.

$\endgroup$
6
  • $\begingroup$ You can use induction. $\endgroup$ Mar 19, 2021 at 8:52
  • $\begingroup$ induction to show which hypothesis? $p$ is not given very clearly here, so I don't see a way to use induction in the level expected of us. $\endgroup$
    – Feelix
    Mar 19, 2021 at 9:05
  • $\begingroup$ Try induction on $n$. $\endgroup$ Mar 19, 2021 at 9:06
  • $\begingroup$ Sorry Yuval, I understand what is induction and induction on $n$, but as of now I fail to clearly see an induction hypothesis which gives a clear path. Your second comment did not add on your first... $\endgroup$
    – Feelix
    Mar 19, 2021 at 9:18
  • 1
    $\begingroup$ Try induction on a statement that would imply $T(n) = \Theta(n^p)$. $\endgroup$ Mar 19, 2021 at 9:32

3 Answers 3

1
$\begingroup$

Let us try to prove that $T(n) \geq cn^p$ by induction. For small enough $c>0$, this would hold for the base case. For the inductive step, $$ T(n) = T(n/3) + T(n/6) + 1 \geq c(n/3)^p + c(n/6)^p + 1 > cn^p. $$ Unfortunately, the same approach doesn't work directly for the upper bound. Instead, we will prove that $T(n) \leq Cn^p - 1$ by induction. For large enough $C>0$, this would hold for the base case. For the inductive step, $$ T(n) = T(n/3) + T(n/6) + 1 \leq C(n/3)^p + C(n/6)^p - 1 = Cn^p - 1. $$


The observant reader would notice that this is a mock proof. Indeed, it is really a mock recurrence, because $n/3$ and $n/6$ in general are not integral. The Akra–Bazzi theorem shows that this doesn't really matter. Instead of finding tricks for solving such recurrence every single time, Akra and Bazzi proved a general theorem which applies in all cases. We should use it instead of spending our time on reproving special cases of it.

$\endgroup$
3
  • $\begingroup$ Thanks, it's nice to see a mock proof for the method in this case. $\endgroup$
    – Feelix
    Mar 19, 2021 at 10:05
  • $\begingroup$ do you think $\frac{1}{3^p}+\frac{1}{6^p}=1$ or $2^p+1=6^p$ is as explicit as we can get in regards to $p$? $\endgroup$
    – Feelix
    Mar 19, 2021 at 10:12
  • $\begingroup$ Probably. But you can estimate it to your heart’s desire. $\endgroup$ Mar 19, 2021 at 11:39
3
$\begingroup$

You could use "guess-and-check": guess the solution to the recurrence, then use induction to prove that it is a solution, i.e., to prove that your solution satisfies the recurrence.

In your case, since you know Akra-Bazzi, your "guess" can actually be obtained through Akra-Bazzi, but you don't have to tell anyone that's how you obtained your guess.

$\endgroup$
0
$\begingroup$

You can find asymptotic of $T(n)$ With finding lower bound and upper bound. So

$T(n)\geq 2T(\frac{n}{6})+1$ that according to master theorem, or recursion tree $T(n)=\Omega(n^{\log_62})=T(n)=\Omega(n^{\frac{1}{1+\log 3}})$

and

$T(n)\leq 2T(\frac{n}{3})+1$. According to master theorem, or recursion tree $T(n)=O(n^{\log_32})=T(n)=O(n^{\frac{1}{log 3}})$.

$\endgroup$
6
  • $\begingroup$ that is not a tight bound, then? $\endgroup$
    – Feelix
    Mar 19, 2021 at 9:19
  • $\begingroup$ Akra-Bazzi gives something of the form $n^p$ where $p=0.489...$, where it is a tight bound $\endgroup$
    – Feelix
    Mar 19, 2021 at 9:21
  • $\begingroup$ $T(n)=\Omega(n^{0.63})$ $\endgroup$
    – user132812
    Mar 19, 2021 at 9:25
  • $\begingroup$ How you understand $O(n^{\log_32})=T(n)$? $\endgroup$
    – zkutch
    Mar 19, 2021 at 10:45
  • $\begingroup$ $T(n)\leq 2T(\frac{n}{3})+1$ with substitution method we have : $2\times 2\times\dots \times 2T(\frac{n}{3^k})+2^{k-1}+...+2+1$ from this we know that $k=\log_3n $ as a result:$T(n)=O(2^{\log_3n})$ $\endgroup$
    – user132812
    Mar 19, 2021 at 11:03

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.