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?
How to solve for p in Akra-Bazzi method for analyzing time complexity?
algorithms;time complexity;asymptotics
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 GoemansWilliamson 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).