6. (3 pts) Fill in the last line (for each complexity class), which shows the size of a problem (M) that can be solved in the same amount of time on a new machine that runs 3 times as fast as the old machine. Solve by hand when you can, use Excel or a calculator when you must. Hint 1: Solving a problem in the same amount of time on the new/faster machine is equivalent to solving a problem that takes 3 times the amount of time on the old machine. Hint 2: write a formula equating problem sizes N and M using the speedup factor and complexity class. For the linear complexity class: c*M=3*c*N; then solve for M. Check that your answers ar reasonable: all Ms should be bigger than N; the higher the complexity class, the closer M should be to N. N = Problem Size Complexity Class Time to Solve on Old Machine (secs) M Solvable in the same Time on a New Machine 3x as Fast 10 O(Log2 N) 1 10% O(N) 1 3 x 100 10% O(N Log2 N) 1 10 O(N2) 1