Answer:
(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.
[tex]log_{2}n[/tex]= 10^9
Let us take the exponential with base 2 of each side of the previous equation:
n =[tex]2^{log_{2n} }[/tex] =[tex]2^{10^9}[/tex] = 4.6130 x 10^391929995 = 4.6130 x [tex]10^{3*10^8}[/tex]
(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= [tex]\sqrt{10^9}[/tex] = 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:
[tex]2^{n}[/tex] = 10^9
Take the logarithm with base 2 of each side of the previous equation:
[tex]log_{2} 2^{n}[/tex]= [tex]log_{2}[/tex] 10^9
Evaluate (round down to the nearest integer!):
n = [tex]log_{2}[/tex] [tex]2^{n}[/tex] = [tex]log_{2}[/tex] 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
