Suppose we have a 1X computer that can execute n statements in time t. Assume that an
Question:
Suppose we have a 1X computer that can execute n statements in time t. Assume that an algorithm which is O(f(n)) requires the execution of a number of statements proportional to f(n).
For example, if A1 ε (n2), then assume that for a problem of size n, the algorithm will execute c*n2 statements (where c is a constant). For simplicity, you can assume c = 1.
a. If we run algorithm A2 ε O(n2) with problem size = n on the 1X computer, how long will it take to run in terms of t?
b. If we run algorithm A3 ε O(nlgn) with problem size = n on the 1X computer, how long will it take to run in terms of t?
c. Suppose an algorithm A4 runs on the 1X computer in time t. When we add 1 more element of data, the same algorithm runs in time 2t. Find the complexity (Big O) of A4.
d. If we want A2 to finish in time t with problem size = n, determine how many times faster then our current 1X computer we need to purchase.
e. How long will it take our 1X computer to run 1,000,000 statements?