Chapter 1, Problem 1P

Program Plan Intro

To complete the table for given function $f\left(n\right)$ and time $t$ .

Explanation of Solution

Given Information:The time taken by algorithm to solve the problems in $f\left(n\right)$ microseconds.

Explanation:

Since 1 microsecond is equal to ${10}^{-6}$ seconds. Therefore, 1 second is equal to ${10}^6$ microseconds.

Consider the function $f\left(n\right)=lg\left(n\right)$ . Now, determine the value of $n$ such that $\lg n<{10}^6$

as follows:

$\begin{array}{l}\lg n<{10}^6\\ 2^{\lg n}<2^{{10}^6}\\ n<2^{{10}^6}\end{array}$

Therefore, the value of $n$ is $2^{{10}^6}$ for 1 second.

Since 1 hour is equal to 3600 seconds. Therefore, 1 hour is equal to $3.6\times {10}^9$ microseconds.

Again, consider the function $f\left(n\right)=lg\left(n\right)$ . Now, determine the value of $n$ such that $\lg n<3.6\times {10}^9$

as follows:

$\begin{array}{l}\lg n<3.6\times {10}^9\\ 2^{\lg n}<2^{3.6\times {10}^9}\\ n<2^{3.6\times {10}^9}\end{array}$

Therefore, the value of $n$ is $2^{3.6\times {10}^9}$ for 1 hour.

Consider a month is equal to 30 days and a year is equal to 365 days.

Similarly, calculate the other values of $t$ in the different functions $f\left(n\right)$ to obtain the correspondinglargest values of $n$ .

Complete the table for different values of $n$

as follows:

$f\left(n\right)$	1 second	1 minute	1 hour	1 day	1 month	1 year	1 century
$\lg 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.15\times {10}^{13}}$	$2^{3.16\times {10}^{15}}$
$\sqrt{n}$	$1\times {10}^{12}$	$3.6\times {10}^{15}$	$1.29\times {10}^{19}$	$7.46\times {10}^{21}$	$6.72\times {10}^{24}$	$9.95\times {10}^{26}$	$9.95\times {10}^{26}$
$n$	$1\times {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.16\times {10}^{15}$
$n\lg n$	62746	2801417	133378058	2755147513	71870856404	797633893349	$6.86\times {10}^{13}$
$n^2$	1000	7745	60000	293938	1609968	5615692	56176151
$n^3$	100	391	1532	4420	13736	31593	146679
$2^n$	19	25	31	36	41	44	51
$n!$	9	11	12	13	15	16	17

Table 1