The complexity of an algorithm often becomes more, not less, significant as computer speeds increase. For example, an aircraft designer runs one simulation each evening between 5 P.M. and 8 A.M. When she gains access to a faster computer, she uses this extra speed to run a larger simulation (one that can provide more detailed results) in the same amount of time. Suppose her current computer can solve a problem of size 100,000 in 15 hours. Assume that the execution time is determined solely by CPU speed; i.e., all other resources such as I/O bandwidth and primary memory are not a constraint on performance. How large a problem can be solved in 15 hours by a computer that is 100 times faster in each of the four cases of the simulation programs time complexity:

(a) (n)

(b) (n log2 n)

(c) (n 2 )

(d) (n 3 )