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…
\[\begin{alignedat}{3} &\lg N &&= 10^6 &&\Rightarrow N = 2^{10^6} \\ &\sqrt N &&= 10^6 &&\Rightarrow N = 10^{12} \\ & N &&= 10^6 &&\Rightarrow N = 10^6 \\ &N \lg N &&= 10^6 &&\Rightarrow N = 62746 \\ &N^2 &&= 10^6 &&\Rightarrow N = 10^3 \\ &N^3 &&= 10^6 &&\Rightarrow N = 10^2 \\ &2^N &&= 10^6 &&\Rightarrow N = 6 \times \lg 10 = 19 \\ &N! &&= 10^6 &&\Rightarrow N = 9 \end{alignedat}\]Among all the calculations, finding \(N\) for \(n \lg n\) and \(n!\) are not so obvious. For these two we’ll need to use calculator or a small snippet of code as shown below.