Question

What is the largest \(n\) for which one can solve within a day using an algorithm that requires \(f\left( n \right)\) bit operations, where each bit operation is carried out in \({10^{ - 11}}\) seconds, with these functions \(f\left( n \right)\)?

\(\begin{array}{l}a)\;\log n\\b)\;1000n\\c)\;{n^2}\\d)\;1000{n^2}\\e)\;{n^3}\\f)\;{2^n}\\g)\;{2^{2n}}\\h)\;{2^{{2^n}}}\end{array}\)

Short answer

a) The largest\(n\)is\({2^{8.64 \times {{10}^{15}}}}\).

b) The largest\(n\)is\(8.64 \times {10^{12}}\).

c) The largest\(n\)is\(92951600\).

d) The largest\(n\)is\(2939388\).

e) The largest\(n\)is\(205197\).

f) The largest\(n\)is\(52\).

g) The largest\(n\)is\(26\).

h) The largest \(n\) is \( \approx 5\).

Step-by-step solution

(a)Step 1: Find bit operations

We find the total number of bit operations that is possible in a day.

\(\begin{array}{l}t = 1s\\T = {10^{ - 11}}s\\\frac{t}{T} = \frac{{86400}}{{{{10}^{ - 11}}}}\\ = 8.64 \times {10^{15}}\end{array}\)

\(8.64 \times {10^{15}}\)bit operations are possible.

\(f(n) = \log n\)

Now we equate\(f(n)\)with the total bit operations possible in a day.

We get,

\(\begin{array}{c}\log n = 8.64 \times {10^{15}}\\n = {2^{\log n}}\\ = {2^{8.64 \times {{10}^{15}}}}\end{array}\)

The largest \(n\) is \({2^{8.64 \times {{10}^{15}}}}\).

b) Step 2: Find bit operations

We find the total number of bit operations that is possible in a day.

\(\begin{array}{l}t = 1s\\T = {10^{ - 11}}s\\\frac{t}{T} = \frac{{86400}}{{{{10}^{ - 11}}}}\\ = 8.64 \times {10^{15}}\end{array}\)

\(8.64 \times {10^{15}}\)bit operations are possible.

\(f(n) = 1000n\)

Now we equate\(f(n)\)with the total bit operations possible in a day.

We get,

\(\begin{array}{c}1000n = 8.64 \times {10^{15}}\\n = \frac{{8.64 \times {{10}^{15}}}}{{1000}}\\ = 8.64 \times {10^{12}}\end{array}\)

The largest \(n\) is \(8.64 \times {10^{12}}\).

c) Step 3: Find bit operations

We find the total number of bit operations that is possible in a day.

\(\begin{array}{l}t = 1s\\T = {10^{ - 11}}s\\\frac{t}{T} = \frac{{86400}}{{{{10}^{ - 11}}}}\\ = 8.64 \times {10^{15}}\end{array}\)

\(8.64 \times {10^{15}}\)bit operations are possible.

\(f(n) = {n^2}\)

Now we equate\(f(n)\)with the total bit operations possible in a day.

We get,

\(\begin{array}{l}{n^2} = 8.64 \times {10^{15}}\\n = \sqrt {8.64 \times {{10}^{15}}} \\ = 92951600\end{array}\)

The largest \(n\) is \(92951600\).

d) Step 4: Find bit operations

We find the total number of bit operations that is possible in a day.

\(\begin{array}{l}t = 1s\\T = {10^{ - 11}}s\\\frac{t}{T} = \frac{{86400}}{{{{10}^{ - 11}}}}\\ = 8.64 \times {10^{15}}\end{array}\)

\(8.64 \times {10^{15}}\)bit operations are possible.

\(f(n) = 1000{n^2}\)

Now we equate\(f(n)\)with the total bit operations possible in a day.

We get,

\(\begin{array}{c}1000{n^2} = 8.64 \times {10^{15}}\partial \\{n^2} = 8.64 \times {10^{12}}\\n = \sqrt {8.64 \times {{10}^{12}}} \\ = 2939388\end{array}\)

The largest \(n\) is \(2939388\).

e) Step 5: Find bit operations

We find the total number of bit operations that is possible in a day.

\[\begin{array}{c}t = 1s\\T = {10^{ - 11}}s\\\frac{t}{T} = \frac{{86400}}{{{{10}^{ - 11}}}}\\ = 8.64 \times {10^{15}}\end{array}\]

\(8.64 \times {10^{15}}\)bit operations are possible.

\(f(n) = {n^3}\)

Now we equate\(f(n)\)with the total bit operations possible in a day.

We get,

\(\begin{array}{c}{n^3} = 8.64 \times {10^{15}}\\n = \sqrt[3]{{8.64 \times {{10}^{15}}}}\\ = 205197\end{array}\)

The largest \(n\) is \(205197\).

f) Step 6: Find bit operations

We find the total number of bit operations that is possible in a day.

\(\begin{array}{c}t = 1s\\T = {10^{ - 11}}s\\\frac{t}{T} = \frac{{86400}}{{{{10}^{ - 11}}}}\\ = 8.64 \times {10^{15}}\end{array}\)

\(8.64 \times {10^{15}}\)bit operations are possible.

\(f(n) = {2^n}\)

Now we equate\(f(n)\)with the total bit operations possible in a day.

We get,

\(\begin{array}{c}{2^n} = 8.64 \times {10^{15}}\\n = \log (8.64 \times {10^{15}})\\ = 52\end{array}\)

The largest \(n\) is \(52\).

g) Step 7: Find bit operations

We find the total number of bit operations that is possible in a day.

\(\begin{array}{c}t = 1s\\T = {10^{ - 11}}s\\\frac{t}{T} = \frac{{86400}}{{{{10}^{ - 11}}}}\\ = 8.64 \times {10^{15}}\end{array}\)

\(8.64 \times {10^{15}}\)bit operations are possible.

\(f(n) = {2^{2n}}\)

Now we equate\(f(n)\)with the total bit operations possible in a day.

We get,

\(\begin{array}{c}{2^{2n}} = 8.64 \times {10^{15}}\\2n = \log (8.64 \times {10^{15}})\\2n = 52\\n = 26\end{array}\)

The largest \(n\) is \(26\).

h) Step 8: Find bit operations

We find the total number of bit operations that is possible in a day.

\(\begin{array}{c}t = 1s\\T = {10^{ - 11}}s\\\frac{t}{T} = \frac{{86400}}{{{{10}^{ - 11}}}}\\ = 8.64 \times {10^{15}}\end{array}\)

\(8.64 \times {10^{15}}\)bit operations are possible.

\(f(n) = {2^{{2^n}}}\)

Now we equate\(f(n)\)with the total bit operations possible in a day.

We get,

\(\begin{array}{l}{2^{{2^n}}} = 8.64 \times {10^{15}}\\{2^n} = \log (8.64 \times {10^{15}})\\{2^n} = 52\\n = \log (52)\end{array}\)

\(\begin{array}{l} = 5.7\\ \approx 5\end{array}\)

The largest \(n\) is \( \approx 5\).