snippetMinor
How to solve for p in Akra-Bazzi method for analyzing time complexity?
Viewed 0 times
methodanalyzingakratimeforsolvehowbazzicomplexity
Problem
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?
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?
Solution
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).
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).
Context
StackExchange Computer Science Q#51905, answer score: 3
Revisions (0)
No revisions yet.