Assume the only computer you have access to can compute 1010

Assume the only computer you have access to can compute 10^10 operations per second, you only have one hour to complete your task, and your task requires f(n) operations to solve an instance of size n. For each of the following functions, what is the largest value of n for which you can complete your task. n^4 n^3 500 n^2 n^1.5 lg n 2^n 2^2^n

Solution

In one second toatl number of operation can be performed 10^10
Total number of operations that can be performed in an hour: 3600x10^10= 36x10^12=3.6x10^13

a) n^4=36*10^12=(2.4495*10^3)^4
n= 2.4495*1000

b) n^3

n^3 = 3.6 * 10^13 operations =36*10^12 = 36*(10^4)^3
Now cube root of 36 is 3.3 0192725
so we can write as
n^3=(3.3 0192725 * 10^4)^3
so
n = 33 019.2725 --> 33019 operations

c) 500*n^2
500*n^2=3.6 * 10^13 operations =36*10^12 = (6*10^6)^2
   so n^2=(6*10^6)^2/500
    = (6*10^6/22.3607)^2
        n= (6*10^6/22.3607)=268327.9146 ==268327 operations

d) 2^n

2^n = 3.6 * 10^13 operations --> log(2^n) = log(3.6 * 10^13 operations) --> n log 2 = log(3.6 * 10^13 operations) --> n = log(3.6 * 10^13) / log(2) = 45.0330621 --> 45 operations

e) 2^2^n

2^2^n = 3.6 * 10^13 operations --> log(2^2^n) = log(3.6 * 10^13 operations) --> 2^n log(2) = log(3.6 * 10^13 operations) --> 2^n = log(3.6 * 10^13 operations) / log(2) --> log(2^n) = n log(2) = log(log(3.6 * 10^13 operations) / log(2)) --> n = (log(log(3.6 * 10^13 operations) / log(2)) / log(2) = 5.49291268 --> 5 operations