2. Suppose we have an O(2n) function that took 3s to execute with n = 20. What would you expect the runtime to be if n = 25? (Note: For an O(2n) function, these input sizes are reasonably large.)

3. Suppose we have an O(n3) function that took 14s to execute with n = 1000. We ran it again with a different input size, and the runtime was approximately 27.34s. What was the input size that second time around?

4. Given the following input sizes (n) and actual runtime (T(n)) for some function, what do you estimate is the big-oh runtime of the function? Additionally, verify that O(1) is an underestimate of the runtime, and show that O(n3) is an overestimate of the runtime.

n T(n) ====================== 2,000 0.016s 2,500 0.0249s 5,000 0.1s 7,500 0.2249s 

5. Given the following input sizes (n) and actual runtime (T(n)) for some function, what do you estimate is the big-oh runtime of the function? Verify your hypothesis using the technique shown in class.

n T(n) ====================== 1,000 0.28s 2,000 0.546s 10,000 2.728s 25,000 6.821s