n log n = c. What are some good approximations of this?

Question

I am currently looking into Big O notation and computational complexity.

Problem 1.1 in CLRS asks what seems a basic question, which is to get an intuition about how different algorithmic complexities grow with the size of the input.

The question asks:

For each function $f(n)$ and time $t$ in the following table, determine the largest size $n$ of a problem that can be solved in time $t,ドル assuming that the algorithm to solve the problem takes $f(n)$ microseconds.

The time periods are 1 second, 1 minute, 1 hour, 1 day, 1 month, 1 year, 1 century.

The functions $f(n)$ are seemingly common time complexities that arise in algorithms frequently, the list being:

$$ \log_2n, \quad \sqrt{n}, \quad n, \quad n \log_2 n, \quad n^2, \quad n^3, \quad 2^n \quad \text{and} \quad n!$$

Most are fairly straightforward algebraic manipulations. I am struggling with two of these, and both for the same reason:

If $c$ is the time in microseconds, the two I am struggling with are $$ n \log_2 n = c$$ $$ n! \sim \sqrt{2\pi n} \left(\frac{n}{e}\right)^n = c$$

For $n!$ I thought of using Stirling's Approximation.

These both require the ability to solve $n \log_2 n = c,ドル with Stirling require a little more manipulation.

Questions

1. As $n \log_2 n$ is not solvable using elementary functions (only Lambert W), what are some good ways to approximate $n log_2 n$? Or how do we implement Lambert W?
2. How do we solve n! = c, necessarily approximately as n grows large. Is Stirling the right way to go, and if so how to solve $\sqrt{2\pi n} \left(\frac{n}{e}\right)^n = c$

---

Here is some python code I put together to complete the table with my current output:

EDIT: Based on a couple of answers, I have used a binary search method (except for lg n). I have edited the code below to reflect this:

+---------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+
| f(n) | 1 sec | 1 min | 1 Hour | 1 Day | 1 Month | 1 Year | 1 Century |
+---------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+
| lg n | 2^(1.0E+06) | 2^(6.0E+07) | 2^(3.6E+09) | 2^(8.6E+10) | 2^(2.6E+12) | 2^(3.2E+13) | 2^(3.2E+15) |
| sqrt(n) | 1.0E+12 | 3.6E+15 | 1.3E+19 | 7.5E+21 | 6.7E+24 | 9.9E+26 | 9.9E+30 |
| n | 1.0E+06 | 6.0E+07 | 3.6E+09 | 8.6E+10 | 2.6E+12 | 3.2E+13 | 3.2E+15 |
| n log n | 62746 | 2.8E+06 | 1.3E+08 | 2.8E+09 | 7.2E+10 | 8.0E+11 | 6.9E+13 |
| n^2 | 1000 | 7745 | 60000 | 293938 | 1.6E+06 | 5.6E+06 | 5.6E+07 |
| n^3 | 100 | 391 | 1532 | 4420 | 13736 | 31593 | 146645 |
| 2^n | 19 | 25 | 31 | 36 | 41 | 44 | 51 |
| n! | 9 | 11 | 12 | 13 | 15 | 16 | 17 |
+---------+-------------+-------------+-------------+-------------+-------------+-------------+-------------+

Python code:

import math
import decimal
from prettytable import PrettyTable
def binary_search_guess(f, t, last=1000):
 for i in range(0, last):
 guess = pow(2,i)
 if f(guess) > t:
 return binary_search_function(f, pow(2,i-1), guess, t)
 return -1 
def binary_search_function(f, first, last, target):
 found = False
 while first<=last and not found:
 midpoint = (first + last)//2
 if f(midpoint) <= target and f(midpoint+1) > target:
 found = True
 else:
 if target < f(midpoint):
 last = midpoint-1
 else:
 first = midpoint+1
 best_guess = midpoint
 return best_guess
def int_or_sci(x):
 if x >= math.pow(10,6):
 x = '%.1E' % decimal.Decimal(x)
 else:
 x = int(x)
 return x
def input_size_calc():
 #Create Pretty Table Header
 tbl = PrettyTable(["f(n)", "1 sec", "1 min", "1 Hour", "1 Day", "1 Month", "1 Year", "1 Century"])
 tbl.align["f(n)"] = "l" # Left align city names
 tbl.padding_width = 1 # One space between column edges and contents (default)
 #Each Time Interval in Microseconds
 tsec = pow(10,6)
 tmin = 60 * tsec
 thour = 3600 * tsec
 tday = 86400 * tsec
 tmonth = 30 * tday
 tyear = 365 * tday
 tcentury = 100 * tyear
 tlist = [tsec,tmin,thour,tday,tmonth,tyear,tcentury]
 #print tlist
 #Add rows 
 #lg n
 f = lambda x : math.log(x,2)
 fn_list = []
 for t in tlist:
 #This would take too long for binary search method
 ans = int_or_sci(t)
 fn_list.append("2^(%s)" % ans)
 tbl.add_row(["lg n",fn_list[0], fn_list[1], fn_list[2], fn_list[3], fn_list[4], fn_list[5], fn_list[6]])
 #sqrt(n)
 f = lambda x : math.pow(x,1/2.0)
 fn_list = []
 for t in tlist:
 fn_list.append(int_or_sci(binary_search_guess(f, t)))
 tbl.add_row(["sqrt(n)",fn_list[0], fn_list[1], fn_list[2], fn_list[3], fn_list[4], fn_list[5], fn_list[6]])
 #n
 f = lambda x : x
 fn_list = []
 for t in tlist:
 fn_list.append(int_or_sci(binary_search_guess(f, t)))
 tbl.add_row(["n",fn_list[0], fn_list[1], fn_list[2], fn_list[3], fn_list[4], fn_list[5], fn_list[6]])
 #n log n
 f = lambda x : x * math.log(x,2)
 fn_list = []
 for t in tlist:
 fn_list.append(int_or_sci(binary_search_guess(f, t)))
 tbl.add_row(["n log n",fn_list[0], fn_list[1], fn_list[2], fn_list[3], fn_list[4], fn_list[5], fn_list[6]])
 #n^2
 f = lambda x : math.pow(x,2)
 fn_list = []
 for t in tlist:
 fn_list.append(int_or_sci(binary_search_guess(f, t)))
 tbl.add_row(["n^2",fn_list[0], fn_list[1], fn_list[2], fn_list[3], fn_list[4], fn_list[5], fn_list[6]])
 #n^3
 f = lambda x : math.pow(x,3)
 fn_list = []
 for t in tlist:
 fn_list.append(int_or_sci(binary_search_guess(f, t)))
 tbl.add_row(["n^3",fn_list[0], fn_list[1], fn_list[2], fn_list[3], fn_list[4], fn_list[5], fn_list[6]])
 #2^n
 f = lambda x : math.pow(2,x)
 fn_list = []
 for t in tlist:
 fn_list.append(int_or_sci(binary_search_guess(f, t)))
 tbl.add_row(["2^n",fn_list[0], fn_list[1], fn_list[2], fn_list[3], fn_list[4], fn_list[5], fn_list[6]])
 #n!
 f = lambda x : math.factorial(x)
 fn_list = []
 for t in tlist:
 fn_list.append(int_or_sci(binary_search_guess(f, t)))
 tbl.add_row(["n!",fn_list[0], fn_list[1], fn_list[2], fn_list[3], fn_list[4], fn_list[5], fn_list[6]])
 print tbl
#PROGRAM BEGIN
input_size_calc()

• Tom van der Zanden: You could approximate $W_n$ by simply doing binary search on the value of $n$ or using a Taylor series. You can extend the factorial function to be continuous, to the gamma function and you can probably find some information on its inverse - but your approach using the Stirling approximation seems fine as well.
• Sagnik: check out this pdf: cs-people.bu.edu/lapets/resource/nlogn.pdf
• David Richerby: @TomvanderZanden Forget $W_n$ -- you can approximate the whole question just by doing a binary search!
• Ben Voigt: Be careful about fractions... using three significant digits is reasonable when n is large, but for small n, make sure to round down to the nearest integer.
• stats_novice_123: @DavidRicherby Can you expand on this please?

Answer 1

The approximate inverse of $c = n\log n$ is $n = c/\log c$. Indeed, for this value of $n$ we have $$ n\log n = \frac{c}{\log c} \log \frac{c}{\log c} = \frac{c}{\log c} (\log c - \log\log c) = c \left(1 - \frac{\log\log c}{\log c}\right). $$ This approximation is usually good enough.

Answer 2

You don't need to approximate anything to solve the exercise. All the functions you're given are monotone so you can just use binary search. That is, to solve $f(n)=c$ for $n,ドル just guess $n=1, 2, 4, 8, \dots$ until you find the first $k$ that 2ドル^k \log 2^k > c$. Then, do ordinary binary search between 2ドル^{k-1}$ and 2ドル^k$. If the solution is $x,ドル this takes roughly 2ドル\log x$ evaluations of $f$.

• stats_novice_123: Wouldn't a binary search on lg n take an infeasible amount of time?
• stats_novice_123: I have edited my code in my question and answer table to reflect this approach. It seems impractical for lg n however, would you agree?
• David Richerby: No, it's fine for solving $\log n = c$. Once you've doubled $\lceil c\rceil$ times, you've overshot, and then you do a binary search between 2ドル^{\lceil c\rceil}$ and 2ドル^{\lfloor c\rfloor}$. That range is about 2ドル^c$ wide, so it takes about $c$ iterations of binary search to find the correct value.
• stats_novice_123: Also lg n = c --> n = 2^c anyway so it is trivial
• David Richerby: OK, I see your point. But, still, you'd only need about 2ドルc$ iterations of the search and, with an efficient bignum library, iterations wouldn't take too long. (And, yeah, as you say, $\log$ is trivially invertible anyway so you can side-step the issue.)