Problems

Problem 1.1¶

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.

	1 second	1 minute	1 hour	1 day	1 month	1 year	1 century
$log_2{n}$	$2^{10^6}$	$2^{6 \times 10^7}$	$2^{3.6 \times 10^9}$	$2^{8.64 \times 10^{10}}$	$2^{2.592 \times 10^{12}}$	$2^{3.1536 \times 10^{13}}$	$2^{3.1536 \times 10^{15}}$
$\sqrt{n}$	$10^{12}$	$3.6 \times 10^{15}$	$1.296 \times 10^{19}$	$7.465 \times 10^{21}$	$6.72 \times 10^{24}$	$9.92 \times 10^{26}$	$9.92 \times 10^{30}$
$n$	$10^6$	$6 \times 10^7$	$3.6 \times 10^9$	$8.64 \times 10^{10}$	$2.59 \times 10^{12}$	$3.15 \times 10^{13}$	$3.15 \times 10^{15}$
$n \cdot log_2{n}$	$62746$	$28014174$	$1.33 \times 10^8$	$2.755 \times 10^{9}$	$7.187 \times 10^{10}$	$7.97 \times 10^{11}$	$6.86 \times 10^{13}$
$n^2$	$1,000$	$7,745$	$60,000$	$293,938$	$1,609,968$	$5,615,692$	$56,156,922$
$n^3$	$100$	$391$	$1,532$	$4,420$	$13,736$	$31,593$	$146,645$
$2^n$	$19$	$25$	$31$	$36$	$41$	$44$	$51$
$n!$	$9$	$11$	$12$	$13$	$15$	$16$	$17$

For $log_2{n}$ , answer is calculated as follows

1 second $$ log_2{n} = 1 \times 10^6 $$

$n = 2^{10^6}$

1 minute $$ log_2{n} = 60 \times 10^6 $$

$n = 2^{6 \times 10^7}$

Similar procedure is used for $\sqrt{n}, n, n^2, n^3$ and $2^n$

For $n \times log_2{n}$ , Fixed-point iteration can be used as $$ f(n) = n \times log_2{n} $$

$n \rightarrow \frac{f(n)}{log_2{n}}$

import math

def fixed_point_iter(fn, first_guess, tolerance = 0.00001):
    guess = first_guess
    while abs(guess - fn(guess)) > tolerance:
        guess = fn(guess)
    return guess

def get_n_for_n_log_n(time):
    log2 = math.log(2)
    return math.floor(
        fixed_point_iter(
            lambda x: time / (math.log(x) / log2),
            100,
            tolerance = 1)
    )

For 1 second, time = 10**6

get_n_for_n_log_n(10**6)

We can also use scipy.optimize.fixed_point function.

from scipy.optimize import fixed_point

def get_n_for_n_log_n(time):
    log2 = math.log(2)
    return math.floor(
        fixed_point(
            lambda x: time / (math.log(x) / log2),
            [100],
            xtol = 0.001
        )
    )

We can retrieve all values:

time_map = {
    "1 second": 10**6,
    "1 minute": 60 * 10**6,
    "1 hour": 60 * 60 * 10**6,
    "1 day": 24 * 60 * 60 * 10**6,
    "1 month": 30 * 24 * 60 * 60 * 10**6,
    "1 year": 365 * 24 * 60 * 60 * 10**6,
    "1 century": 100 * 365 * 24 * 60 * 60 * 10**6
}
for label, time in time_map.items():
    n = get_n_for_n_log_n(time)
    print(f'For {label}, n = {n}')

For 1 second, n = 62746
For 1 minute, n = 2801417
For 1 hour, n = 133378059
For 1 day, n = 2755147515
For 1 month, n = 71870856441
For 1 year, n = 797633893656
For 1 century, n = 68610956766262

For $n!$ , we can simply try values since we do not cross $20!$