Order-of-growth of selection sort is quadratic, it takes 2secs to sort 100 elements, what will be the expected completion time to sort 200 elements? 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&nbsp;x&nbsp;(1002)&nbsp;&nbsp;     -------------(1)

x = k&nbsp;x&nbsp;(2002)&nbsp;&nbsp;     -------------(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!
First off, that's a less than wonderful question.

Second: If the running time is indeed quadratic (with no linear term), the best answer is 8 seconds, not 4 seconds.  Suppose the running time is $T(n) = c \cdot n^2$ for some constant $c$.  Then we know $T(100) = $ 2 seconds.  One can show that

$$T(200) = c \cdot 200^2 = c \cdot 4 \cdot 100^2 = 4 \times T(100),$$

so it follows that $T(200) =$ 8 seconds.

That said, I still don't like the question very much.  Usually when we say that an algorithm has quadratic running time, we mean that its running time is in $\Theta(n^2)$.  That means the running time could be something like $T(n) = c_1 \cdot n^2 + c_2 \cdot n$.  If the running time looks like that, then we don't have enough information to conclude what the running time will be for $n=200$.