Problem 1-1

Comparison of running times

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.

I wrote running_time_compare.py to solve this table. The numbers got pretty big, so I used some techniques to simplify the figures.

\[\newcommand\T{\Rule{0pt}{1em}{.3em}} \begin{array}{|c|c|c|c|c|c|c|c|} \hline & \textrm{1 second} & \textrm{1 minute} & \textrm{1 hour} & \textrm{1 day} & \textrm{1 month} & \textrm{1 year} & \textrm{1 century} \\\hline \lg n \T & 2^{10^6} \T & 2^{6 \cdot 10^7} \T & 2^{3.6 \cdot 10^9} \T & 2^{8.64 \cdot 10^{10}} \T & 2^{2.59 \cdot 10^{12}} \T & 2^{3.15 \cdot 10^{13}} \T & 2^{3.15 \cdot 10^{15}} \\\hline \sqrt{n} \T & 10^{12} \T & 3.6 \cdot 10^{15} \T & 1.3 \cdot 10^{19} \T & 7.47 \cdot 10^{21} \T & 6.72 \cdot 10^{24} \T & 9.95 \cdot 10^{26} \T & 9.96 \cdot 10^{30} \\\hline n \T & 10^6 \T & 6 \cdot 10^7 \T & 3.6 \cdot 10^9 \T & 8.64 \cdot 10^{10} \T & 2.6 \cdot 10^{12} \T & 3.15 \cdot 10^{13} \T & 3.15 \cdot 10^{15} \\\hline n \lg n \T & 62,746 \T & 2,801,417 \T & 133,378,058 \T & 2,755,147,513 \T & 71,870,856,404 \T & 797,633,893,349 \T & 68,610,956,750,570 \\\hline n^2 \T & 1,000 \T & 7,745 \T & 60,000 \T & 293,398 \T & 1,609,968 \T & 5,615,692 \T & 56,156,922 \\\hline n^3 \T & 100 \T & 391 \T & 1,532 \T & 4,420 \T & 13,736 \T & 31,593 \T & 146,645 \\\hline 2^n \T & 19 \T & 25 \T & 31 \T & 36 \T & 41 \T & 44 \T & 51 \\\hline n! \T & 9 \T & 11 \T & 12 \T & 13 \T & 15 \T & 16 \T & 17 \\\hline \end{array}\]

running_time_compare.py

import math


def generate_time_array():
    second = 1000000
    minute = 60 * second
    hour = 60 * minute
    day = 24 * hour
    month = 30 * day
    year = 365 * day
    century = 100 * year
    return [second, minute, hour, day, month, year, century]


def sqrt_n(time):
    return time ** 2


def n(time):
    return time


def n_lg_n(time):
    time_taken, n = 0, 0
    initial_n = 1
    # overshoot the first n
    while time_taken <= time:
        initial_n *= 10
        time_taken = (initial_n * math.log(initial_n, 2))
    # now double back iteratively and determine the specific location
    n = 0
    for x in range(len(str(initial_n))):
        o = initial_n // 10 ** x
        n = n_lg_n_helper(time, o, n)
    return n


def n_lg_n_helper(time, o, n_so_far):
    time_taken = 0
    n = n_so_far
    while time_taken < time:
        n += o
        time_taken = (n * math.log(n, 2))
    return n - o


def n_squared(time):
    time_taken, n = 0, 0
    while time_taken <= time:
        n += 1
        time_taken = n ** 2
    return n-1


def n_cubed(time):
    time_taken, n = 0, 0
    while time_taken <= time:
        n += 1
        time_taken = n ** 3
    return n-1


def two_to_the_n(time):
    time_taken, n = 0, 0
    while time_taken <= time:
        n += 1
        time_taken = 2 ** n
    return n-1


def n_factorial(time):
    time_taken, n = 0, 0
    while time_taken <= time:
        n += 1
        time_taken = math.factorial(n)
    return n-1


time_array = generate_time_array()
time_array_names = ["second", "minute", "hour", "day", "month", "year", "century"]

print("lg(n)")
for i in range(len(time_array_names)):
    print(time_array_names[i] + ": 2^" + str(time_array[i]))

print("sqrt(n)")
for i in range(len(time_array_names)):
    print(time_array_names[i] + ": " + str(sqrt_n(time_array[i])))

print("n")
for i in range(len(time_array_names)):
    print(time_array_names[i] + ": " + str(n(time_array[i])))

print("n lg(n)")
for i in range(len(time_array_names)):
    print(time_array_names[i] + ": " + str(n_lg_n(time_array[i])))

print("n^2")
for i in range(len(time_array_names)):
    print(time_array_names[i] + ": " + str(n_squared(time_array[i])))

print("n^3")
for i in range(len(time_array_names)):
    print(time_array_names[i] + ": " + str(n_cubed(time_array[i])))

print("2^n")
for i in range(len(time_array_names)):
    print(time_array_names[i] + ": " + str(two_to_the_n(time_array[i])))

print("n!")
for i in range(len(time_array_names)):
    print(time_array_names[i] + ": " + str(n_factorial(time_array[i])))