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.

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.

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