Determining asymptotic running time by profiling The purpose of performance proﬁling is to measure program performance. One part of your PA1 assignment asked to measure performance of your d-smooth algorithm to verify if the running time of the program corresponds to the desired $O(n \log n)$. Assume that you have performed an experimental analysis of an algorithm, and proﬁling returned the following times: for instances of sizes $2^{10}, 2^{11}, 2^{12}, 2^{13}, 2^{14}$ the corresponding times are approximately 300, 500, 1100, 2900, 8300 milliseconds. There is an extra overhead resulting from clocking program performance and functions calls, and this overhead has to be considered in analyzing data. That is, the measured time consists of two components: the time for executing the operations, plus the overhead from proﬁling. The estimated overhead due to proﬁling is about 200 milliseconds independently of the input size. (that is, 200 is always an additive “constant”).
  Based on these experimental results, what is the running time for executing operations in this algorithm? ($c$ is a constant) In particular, is your implementation running in $O(n \log n)$?
  
  
  $c \log n$
  $c n$ 
  $c n \log n$
  $c n\sqrt{n}$ &lt;----- Correct answer
  $c n^2$
  


(editor's note: I changed 81200 to 8300; the setters added 200 to 81000 instead of to 8100)

Why is $c n\sqrt n$ the correct answer?
If you remove the 200ms overhead, you get
$$
\begin{array}{c|ccccc}
n &amp; 2^{10} &amp; 2^{11} &amp; 2^{12} &amp; 2^{13} &amp; 2^{14} \\
t &amp; 100 &amp; 300 &amp; 900 &amp; 2700 &amp; 8100
\end{array}
$$
This shows that when $n = 2^{10+k}$, $t = 100 \cdot 3^k$. You take it from here. (You won't get $cn^{3/2}$, by the way! The setters made a mistake.)