Solving a recurrence of uneven subproblems without Akra-Bazzi

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.

• You can use induction. Mar 19 '21 at 8:52
• 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. Mar 19 '21 at 9:05
• Try induction on $n$. Mar 19 '21 at 9:06
• 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... Mar 19 '21 at 9:18
• Try induction on a statement that would imply $T(n) = \Theta(n^p)$. Mar 19 '21 at 9:32

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.

• Thanks, it's nice to see a mock proof for the method in this case. Mar 19 '21 at 10:05
• 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$? Mar 19 '21 at 10:12
• Probably. But you can estimate it to your heart’s desire. Mar 19 '21 at 11:39

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.

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

• that is not a tight bound, then? Mar 19 '21 at 9:19
• Akra-Bazzi gives something of the form $n^p$ where $p=0.489...$, where it is a tight bound Mar 19 '21 at 9:21
• $T(n)=\Omega(n^{0.63})$
– user132812
Mar 19 '21 at 9:25
• How you understand $O(n^{\log_32})=T(n)$? Mar 19 '21 at 10:45
• $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})$
– user132812
Mar 19 '21 at 11:03