How to solve for p in Akra-Bazzi method for analyzing time complexity?

Question

Every single online resource I've looked up on Akra-Bazzi method appears to skip over the same step: They say you have to solve for $p$ without explaining how. If you look up the various PDFs and webpages online, they all basically say "Here's the equation. Solve for $p$. It equals (whatever). Moving on now to the integral..." without explaining how they solved the equation.

If I had to figure it out I could use a binary search but I imagine there is a more mathematical way to get an exact answer.

It is not at all obvious to me how you're supposed to solve for p.

That is:

$$ a_1 b_1^p + a_2 b_2^p + a_3 b_3^p + \dots + a_k b_k^p = 1, $$

Where all $a_i$ terms are positive and all $b_i$ terms are fractional ($0 < b_i < 1$).

How can you solve for $p$ by hand?

Answer 1

You don't solve for $p$ by hand. You use a computer to get a numerical solution. In general, there is no reason to expect that $p$ have some nice form.

Since the left-hand side of the equation is monotone decreasing, there is at most one solution. Furthermore, when $p \to -\infty$ the left-hand side tends to $\infty$, whereas when $p \to \infty$ it tends to $0$. This shows that a solution does exist. The computer can find it using standard root-finding methods.

This kind of situation is encountered in many other places in computer sciences. Here are two examples:

• The approximation ratio of the Goemans–Williamson algorithm is $$ \min_{0 \leq \theta \leq \pi} \frac{2}{\pi} \frac{\theta}{1-\cos\theta} \approx 0.878, $$ which doesn't have a closed form. Surprisingly, assuming the unique games conjecture, this approximation ratio is the best that polynomial time algorithms can achieve in the worst case.

• Running times of fast matrix multiplication algorithms are of the form $O(n^\rho)$ where $\rho$ is in simple cases the solution of an equation similar to the one you describe, and in other cases the solution of a much more complicated optimization problem. Again, there is no closed form for $\rho$ in most cases (other than Strassen's algorithm, perhaps).