I’m trying to calculate input size limits for an n lg n algorithm and have discovered that I don’t remember how to solve such an equation.
For example, given:
n lg n = 1000000
How do I solve for n, which in this case seems to be around 62K?
I’ve tried googling this and haven’t had any luck finding search terms that work.
Thanks for any help!
I’m sorry to say, but I’m afraid you’re stuck with doing this numerically – you can’t solve it analytically, since n lg(n) doesn’t have an inverse.
I use as a very rough approximation for m = n log n then n is about m/log m.
(Good enough for “Big Oh” purposes.)
It has an inverse; just not one that you might have a nice name for, other than “the inverse of n lg(n)”. If no one ever bothered to give arctangent a nice name, you’d be just as inclined to say tangent doesn’t have an inverse, though clearly, it does.
The nice thing here is that n log n is one-to-one, so you don’t have to worry about multiple roots. Try a few rounds of gradient descent on (n log n - 1000000)[sup]2[/sup] to get a rough approximation of the root, and then pass that into Newton’s method as your initial estimate if you need better accuracy.
That’s too rough to use for numerical calculations.
How accurate do you need the limits? If you just need a crude upper or lower bound, then use ftg’s estimate to get
n[sub]0[/sub] = m / log(m)
or iterate it once to get
n[sub]1[/sub] = m / log(n[sub]0[/sub]) = m / log(m / log(m) )
The errors will have opposite sign, so the true n will be between n[sub]0[/sub] and n[sub]1[/sub].