PROBLEM 5 (20 points): (estimation of asymptotic runtime from experiments) Log into bert or bertvm. In the directory ~jlillis/CS251-public you will find an executable called mystery (but no source code!). The program takes a single command line argument N ("problem size"). When you run the program it does some mysterious computations and eventually terminates. When it terminates it prints out the (approximate) CPU time taken by the run in seconds. For example if you do this: ~jlillis/CS251-public/mystery 2000 it will run with N=2000 and then report the elapsed CPU time in seconds. Your job: do some experiments by running the mystery program for a range of values of N and try to come up with a conjecture on the asymptotic runtime of the program as a function of N by doing some analysis. Assumption/hint: the actual runtime has the form (Nd) for some d. You are trying to figure out what d is.

SHOW YOUR WORK: describe the experiments you did and how you arrived at your final conclusion.