8
$\begingroup$

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

2 Answers 2

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
0
1
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\begingroup$ Wouldn't a binary search on lg n take an infeasible amount of time? $\endgroup$
    – stats_novice_123
    Aug 2, 2015 at 18:29
  • $\begingroup$ 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? $\endgroup$
    – stats_novice_123
    Aug 2, 2015 at 18:50
  • $\begingroup$ 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. $\endgroup$
    – David Richerby
    Aug 2, 2015 at 19:10
  • 1
    $\begingroup$ Also lg n = c --> n = 2^c anyway so it is trivial $\endgroup$
    – stats_novice_123
    Aug 2, 2015 at 19:19
  • 2
    $\begingroup$ 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.) $\endgroup$
    – David Richerby
    Aug 2, 2015 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.