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.

In $f(n)$ microseconds, largest size of problem that can be solved is $n$. To find the largest size of problem that can be solved in time $t$, we need to solve the following equation for $n$ $$f(n) = t \text{ in microseconds}$$

Once we calculate the largest size of problem that can be solved in $1$ second (let’s say $N$), it is easy to do so for other time units. But remember, $N$ is an integer, so you should not just multiply $N$ with conversion factor- the answer will be off by huge amount for higher time complexities. Instead you should multiply in the beginning of the calculation.

Here are the calculations for largest size of problem that can be run in $1$ second…

 $\lg n$ $\lg N = 10^6 \Rightarrow N = 2^{10^6}$ $\sqrt n$ $\sqrt N = 10^6 \Rightarrow N = 10^{12}$ $n$ $N = 10^6$ $n \lg n$ $N \lg N = 10^6 \Rightarrow N = 62746$ [code] $n^2$ $N^2 = 10^6 \Rightarrow N = 10^3$ $n^3$ $N^3 = 10^6 \Rightarrow N = 10^2$ $2^n$ $2^N = 10^6 \Rightarrow N = 6 \times \lg 10 = 19$ $n!$ $N! = 10^6 \Rightarrow N = 9$ [code]

Python Code: