The above is an MCQ from an online quiz given by my Algorithm lecturer. The available options are 6secs, 4secs, 12secs and 20secs.
The answer I selected was 12secs and it was rejected. The lecturer said the answer should be 4secs and then I started to prove that the answer is greater than or equal to 8secs in the following ways.
1. Using Proportions
T = kN2, where k is an arbitrary constant
2 = k x (1002) -------------(1)
x = k x (2002) -------------(2)
(2)/(1) implies, x/2 = 2002/1002 = 22 = 4,
i.e. x/2 = 4 but x = 2 x 4 = 8secs
2. Using 'doubling hypothesis'
NOTE: This is almost identical to the first proof.
Running Time = aNb, where b = 2
2 = 1002a, and a = 2/1002
Then again, Time = aN2 = (2/1002)N2 =(2/1002) x 2002 = 2 x 4 = 8secs
3. Using a slide from a reliable source
As you can see the ratio T(2N)/T(N) = 4 for Selection Sort
Suppose the answer is 4secs,
T(2N)/T(N) = 4/2 = 2 and the order-of-growth becomes linear and this proves the answer 4sec is wrong.
Whereas when you substitute the answer 8secs,
T(2N)/T(N) = 8/2 = 4 and proves that the order-of-growth is quadratic according to this slide.
4. By ploting the curve on a graph
Both the points (100,2) and (200,8) satisfies Y=mX2 and m = 2 x 10-2, and I proved it through equations as well to show that the curve is quadratic and not cubic or else. Also plotted the straight line for the points (100,2) and (200,4).
Finally, the lecturer agrees that the answer should be 8secs but since that option is missing I should select the closest approximation which is 6secs.
But my point is the running time should be greater than or equal to 8secs and at the same time closest to 8secs because there are other basic operations involved as well like variable declaration, initiation, comparison, swap function and for small inputs the time taken for those aren't negligible. So the answer 12secs is my answer in the given context.
Although we can't tell the exact running time, what do you think is the possible range for running time? and, is my argument valid or not?
I thank you in advance!