# \[Math\] Solving equations that contain logarithms

**URL:** <https://boards.straightdope.com/t/math-solving-equations-that-contain-logarithms/462500>\
**Category:** Factual Questions\
**Created:** [September 7, 2008, 4:45pm UTC](https://boards.straightdope.com/t/math-solving-equations-that-contain-logarithms/462500 "2008-09-07T16:45:22Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![meara](https://avatars.discourse-cdn.com/v4/letter/m/df705f/32.png) [@meara](https://boards.straightdope.com/u/meara)\
**Post date:** [September 7, 2008, 4:45pm UTC](https://boards.straightdope.com/t/math-solving-equations-that-contain-logarithms/462500/1 "2008-09-07T16:45:22Z")

</div>

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!

---

<div class="post-metadata">

**Author:** ![Half\_Man\_Half\_Wit](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/half_man_half_wit/32/21766_2.png) [@Half\_Man\_Half\_Wit](https://boards.straightdope.com/u/Half_Man_Half_Wit)\
**Post date:** [September 7, 2008, 5:38pm UTC](https://boards.straightdope.com/t/math-solving-equations-that-contain-logarithms/462500/2 "2008-09-07T17:38:06Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\
**Post date:** [September 7, 2008, 5:51pm UTC](https://boards.straightdope.com/t/math-solving-equations-that-contain-logarithms/462500/3 "2008-09-07T17:51:27Z")

</div>

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.)

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [September 7, 2008, 7:39pm UTC](https://boards.straightdope.com/t/math-solving-equations-that-contain-logarithms/462500/4 "2008-09-07T19:39:29Z")

</div>

> [@Half\_Man\_Half\_Wit](#):
>
> 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.

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.

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [September 7, 2008, 8:07pm UTC](https://boards.straightdope.com/t/math-solving-equations-that-contain-logarithms/462500/5 "2008-09-07T20:07:28Z")

</div>

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.

> [@ftg](#):
>
> 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.)

That’s too rough to use for numerical calculations.

---

<div class="post-metadata">

**Author:** ![ZenBeam](https://avatars.discourse-cdn.com/v4/letter/z/3ab097/32.png) [@ZenBeam](https://boards.straightdope.com/u/ZenBeam)\
**Post date:** [September 7, 2008, 8:43pm UTC](https://boards.straightdope.com/t/math-solving-equations-that-contain-logarithms/462500/6 "2008-09-07T20:43:29Z")

</div>

> [@](#):
>
> I’m trying to calculate input size limits for an n lg n algorithm

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].
