Solving a recurrence of uneven subproblems without Akra-Bazzi

Question

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.

• Yuval Filmus: You can use induction.
• Feelix: 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.
• Yuval Filmus: Try induction on $n$.
• Feelix: 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...
• Yuval Filmus: Try induction on a statement that would imply $T(n) = \Theta(n^p)$.

Answer 1

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.

• Feelix: Thanks, it's nice to see a mock proof for the method in this case.
• Feelix: 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$?
• Yuval Filmus: Probably. But you can estimate it to your heart’s desire.

Answer 2

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.

Answer 3

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

• Feelix: that is not a tight bound, then?
• Feelix: Akra-Bazzi gives something of the form $n^p$ where $p=0.489...,ドル where it is a tight bound
• user132812: $T(n)=\Omega(n^{0.63})$
• zkutch: How you understand $O(n^{\log_32})=T(n)$?
• user132812: $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})$