I was trying to solve an equation of the form for , but couldn’t figure out how to do the algebra needed to isolate . The actual problem was to find when an algorithm with runtime performance would have a shorter runtime than an algorithm that is .

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 using algebraic and logarithmic operations and then . Note that the solution may not be unique; 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 , and given that grows rather quickly, it is sufficient to use a spreadsheet to calculate the two sides of the original equation for all small values of .

### Like this:

Like Loading...

*Related*

Tags: math

This entry was posted on October 18, 2009 at 7:59 pm and is filed under technical. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply