Assume that we have recorded the following data when timing three methods (measured in milliseconds). Based on these times (which are measured and therefore approximate, so don’t expect perfect results), fill in an estimate for the complexity class (one of the standard ones) for each method and fill in an estimate for the running time when N = 1,600. N Time: Method 1 Time: Method 2 Time: Method 3
100 300 20 20
200 694 76 22
400 1196 325 20
800 2395 1178 19
1600

Complexity Class estimate