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

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?

• You might get lucky and "see" what $p$ satisfies the equation and thus "solve by hand". Most of the time you will have to use a numerical method like Newton's – vonbrand Jan 15 '16 at 20:56

## 1 Answer

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

• So in practice you would not use something like binary search necessarily? Or are you saying you would? I can't tell if this counts as a "numeric" method but I assume it does. – AJJ Jan 15 '16 at 21:08
• There are several numerical methods for solving equations. Your computer algebra system will use one of them to solve the equation for you. I personally don't care which. – Yuval Filmus Jan 15 '16 at 21:09
• What does the computer algebra system use to solve the equation? (e.g. Wolfram Alpha or Mathematica) – AJJ Jan 15 '16 at 21:09
• It depends on the computer algebra system and on its user. If you're interested, take a course in numerical analysis or read the source code of SAGE. The phrase numerical methods means that the computer doesn't use a formula. – Yuval Filmus Jan 15 '16 at 21:10