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.

T(2N)/T(N) ratio

4. By ploting the curve on a graph

T(2N)-T(N) 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!

  • 2
    $\begingroup$ Your lecturer made a mistake. The intended answer should have been 8 seconds. $\endgroup$ Mar 24 '17 at 21:20

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$.

  • $\begingroup$ I preferred "a crummy question" :-) $\endgroup$
    – gnasher729
    Mar 24 '17 at 22:23
  • 1
    $\begingroup$ If T(100) = 2 seconds for selection sort of 100 items, then something very unusual is going on here. 2 seconds is an awful long time for that kind of operation, so I wouldn't dare making any predictions for T(200) until I understood where the enormous time for T(100) comes from. $\endgroup$
    – gnasher729
    Mar 24 '17 at 22:28

Both answers 4secs and 6secs given by the lecturer are correct since those are the only possibilities.

My friend derived to this conclusion based on the following calculation,

T(N) = a(N2) + bN + c = 2, where 'bN+ c' is not neglegible for small input size like 200 elements.

T(2N) = 4a(N2) + 2bN + c  <  4a(N2) + 4bN +4c

                                    T(2N) < 4[a(N2) + bN + c ]

                                               < 4T(N)

                                               < 4 x 2

                                    T(2N) < 8secs

At the same time ,

                                    T(2N) > T(N)

                                    T(2N) > 2secs

This gives the range for T(2N) as below,

2secs < T(2N) < 8secs

Since both of those answers are within this range, this proves my argument is invalid.

  • $\begingroup$ There is no reason to assume that T (n) is a polynomial, no reason to assume that b and c are positive. You cannot even assume that T (200) > T (100). $\endgroup$
    – gnasher729
    Mar 26 '17 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.