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

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.

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

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():
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

#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, fn_list, fn_list, fn_list, fn_list, fn_list, fn_list])

#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, fn_list, fn_list, fn_list, fn_list, fn_list, fn_list])

#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, fn_list, fn_list, fn_list, fn_list, fn_list, fn_list])

#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, fn_list, fn_list, fn_list, fn_list, fn_list, fn_list])

#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, fn_list, fn_list, fn_list, fn_list, fn_list, fn_list])

#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, fn_list, fn_list, fn_list, fn_list, fn_list, fn_list])

#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, fn_list, fn_list, fn_list, fn_list, fn_list, fn_list])

#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, fn_list, fn_list, fn_list, fn_list, fn_list, fn_list])

print tbl

#PROGRAM BEGIN
input_size_calc()

• 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. – Tom van der Zanden Aug 1 '15 at 17:49
• check out this pdf: cs-people.bu.edu/lapets/resource/nlogn.pdf – Sagnik Aug 1 '15 at 19:03
• @TomvanderZanden Forget $W_n$ -- you can approximate the whole question just by doing a binary search! – David Richerby Aug 1 '15 at 21:07
• 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. – Ben Voigt Aug 2 '15 at 3:21
• @DavidRicherby Can you expand on this please? – stats_novice_123 Aug 2 '15 at 14:55

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.
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$.
• 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. – David Richerby Aug 2 '15 at 19:10
• OK, I see your point. But, still, you'd only need about $2c$ 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.) – David Richerby Aug 2 '15 at 19:23