[Solved]: n log n = c. What are some good approximations of this?

Problem Detail: 

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

Asked By : stats_novice_123

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44944