Solving equations with exponential and polynomial functions of x: the Product Log Function

I was trying to solve an equation of the form $cx^p=q^x$ for $x$, but couldn’t figure out how to do the algebra needed to isolate $x$.  The actual problem was to find when an algorithm with $O(n^2)$ runtime performance would have a shorter runtime than an algorithm that is $O(2^n)$.

Text-based searches weren’t turning up anything, so I tried to see how Wolfram Alpha would solve it.  Turns out there is a neat tool called the Product Log function, aka the Lambert W function, that can be used to find a closed-form solution to this equation.  The Wikipedia article explains the solution method, but you basically need to reorganize the original equation into the form $y = x e^x$ using algebraic and logarithmic operations and then $x=W(y)$.  Note that the solution may not be unique; $W(y)$ is a multivalued function.

Of course, for my original problem where I was actually trying to find the closest integer less than or equal to $x$, and given that $q^x$ grows rather quickly, it is sufficient to use a spreadsheet to calculate the two sides of the original equation for all small values of $x$.

Tags: