Question

1) Let A and B be two programs that perform the same task. Let tA (n) and tB (n), respectively, denote their run times. For each of the following pairs, find the range of n values for which program A is faster than program B. Show the values for each and how you obtained them (justify).

a) tA (n) =1000n , tB (n) =10n^2

b) tA (n) = 2n^2 , tB (n) = n ^3

c) tA (n) = 2^n , tB (n) =100n

d) tA (n) =1000n logn , tB (n) = n^2

Answer 1

The best way of calculating this is by using an Excel sheet or a programming language with a looping construct. For the first column in excel I am putting value of n. Next column as tA(n), next as tB(n) and last column as tA(n)-tB(n). When the value of 4th column is negative it is when tA(n) is faster as compared to tB(n). The thing with excel is you can easily expand using the small dot at the bottom right of the cell. With a programming language you just need to add an if statement to find a starting point and by looking at functions you can detemined if there will be an ending point or not (if tA(n) is asymptotically smaller as compared to tB(n) then there will be no ending point).

a. n = 101 to infinity

b. n = 3 to infinity

c. n = 0 to 9

d. n = 3551 to infinity