What is the largest n for which one can solve within one second a problem using an algorithm that requires f(n) bit operations, where each bit operation is carried out in 10–9 seconds, with the functions f(n) below? Click and drag the correct answer to complete each statement.

a) For f(n) = log n, the largest n is =
b) For f(n) = n, the largest n is =
c) For f(n) = n log n, the largest n is =
d) For f(n) = n^2, the largest n is =
e) For f(n) = 2^n, the largest n is =
f) For f(n) = n!, the largest n is =

(a) Each bit operation is carried out in 10^-9 seconds: T = 10^-9 seconds.  

The algorithm can take at most t = 1 second, while there are t/T = 1/10^-9  

10^9 possible bit operations in t = 1 second.

Algorithm requires f(n) = log n bit operations:

log n = 10^9

Note: The logarithm has base 2, because bits only have 2 possible values.

= 10^9

Let us take the exponential with base 2 of each side of the previous equation:  

n = = = 4.6130 x 10^391929995 = 4.6130 x

(b) Each bit operation is carried out in 10^-9 seconds: T = 10^-9 seconds.  

The algorithm can take at most t = 1 second. while there are t/T = 1/ 10^-9  

10^9 possible bit operations in t = 1 second. Algorithm requires f(n) = n bit operations:

n = 10^9  

(c) Each bit operation is carried out in 10^-9 seconds: T = 10^-9 seconds. The algorithm can take at most t = 1 second, while there are t/T = 1/10^-9

10^9 possible bit operations in t = 1 second.  

Algorithm requires f(n) = nlogn bit operations:

n log n = 10^9

Note: The logarithm has base 2, because bits only have 2 possible values.  

n is then the product of 10^9 and the logarithm of 2, divided by the Lambert W function of the product in the numerator.

n = 10^9 * log(2)/W(10^9*log(2)

  = 3.96 * 10^7

Note: You need to use technology to evaluate the Lambert W function.  

(d) Each bit operation is carried out in 10^-9 seconds: T = 10^-9 seconds.  

The algorithm can take at most t = 1 second, while there are t/T = 1/10^-9 =  

10^9 possible bit operations in t = 1 second.

Algorithm requires f(n) = n^2 bit operations:

n^2 = 10^9

Take the square root of each side of the previous equation (round down to the nearest integer!):  

n=   = 3.16 * 10^4

(e) Each bit operation is carried out in 10^-9 seconds: T = 10^-9 seconds.  

The algorithm can take at most t = 1 second, while there are t/T = 1/10^-9  =

10^9 possible bit operations in t = 1 second.

Algorithm requires f(n) = 2 bit operations:

= 10^9

Take the logarithm with base 2 of each side of the previous equation:

= 10^9

Evaluate (round down to the nearest integer!):

n = = 10^9 = 29  

(f) Each bit operation is carried out in 10^-9 seconds: T = 10^-9 seconds. The algorithm can take at most t = 1 second, while there are t/T = 1/10^-9 =10^9 possible bit operations in t = 1 second.  

Algorithm requires fin) = n! bit operations:

n! = 10^9

Since 12! = 9.79 x 10^8 and 13! = 6.23 x 10^9, we know 12! < 109 < 13!. n is then the lower limit  

n = 12