Algorithms Homework Exercise 2.2
Suppose you have algorithms with the six running times listed below. (Assume these are the exact number of operations performed as a function of the input size n.) Suppose you have a computer that can perform 1010 operations per second, and you need to compute a result in at most an hour of computation. For each of the algorithms, what is the largest input size n for which you would be able to get the result within an hour?
In the question, the computer can perform 1010 per second. Therefore we need to find how many second in one hour. 1 hour equals 60 minutes, each minute has 60 seconds; 60 minutes * 60 seconds = 3600 seconds.
Question a) n2
Solution: a) n2 ≤ 3600 x 1010 n ≤ 60 x 105 = 6.000.000 operations.
Question b) n3
Solution: b) n3 ≤ 3600 x 1010 n ≤ 361/3 x 104 3.3019 x 104 = 33019 operations.
Question c) 100n2
Solution: c) 100n2 ≤ 3600 x 1010 n2 ≤ 36 x 1010 n ≤ 6 X 105 = 600,000 operations
Question d) n log n
Solution:d) n log n ≤ 3600 x 1010 n ≤ 1.29 x 1012 = 1290000000000 operations matlab e^(w(36×10^12)) Lamber w equation.
Question e) 2n
Solution: e) 2n ≤ 3600 x 1010 log(2n) = log(3600 x 1010) n log 2 = log(3.6 x 1013) n = log(3.6 x 1013) / log(2) = 45.0330621 = 45 operations
Question f) 2^(2^n )
Solution:f) 2^(2^n )= 3600 x 1010 log(2^(2^n )) = log(3600 x 1010) 2n log(2) = log(3.6 x 1013) 2n = log(3.6 x 1013 ) / log(2) log(2n) = n log(2) = log(log(3.6 x 1013 ) / log(2)) n = (log(log(3.6 x 1013) / log(2)) / log(2) = 5.49291268 = 5 operations