0
$\begingroup$

I am dealing with a sample exam question that I cannot understand which is as follows:

Selection sort takes one millisecond to sort 1000 items (worst-case time) on a particular computer. Estimate the amount of time it would take to sort 100,000 items. If Mergesort took 1 second for 100 items and 15 seconds for 1000 items, how long would you expect it to take for 1,000,000?

Now, I know that selection sort has worst-case upper bound of $O(n^2)$. So as size of input $n$ increases, $f(n)$ increases in a quadratic manner. So I understand the concept of it but I don't understand how to use it to solve for how much time it would take for 100,000 items (100 times the original input). How would I solve it?

$\endgroup$
  • $\begingroup$ They want you to apply rule of three under ridiculous assumptions. (There are unknown lower-order terms and constant factors hidden in that $O(n^2)$. ) The question is senseless. $\endgroup$ – Raphael Oct 18 '16 at 0:08
  • $\begingroup$ I'm sorry but I haven't heard of the rule of three before. Could you show me how I can use it to solve this question? $\endgroup$ – learnerX Oct 18 '16 at 0:10
  • $\begingroup$ I'm sure you have. But no, it can't be used to really answer this question. And no, I won't be accomplice in teaching you wrong things. What your teacher wants you to calculate has nothing to do with how algorithm analysis or even Landau notation works. $\endgroup$ – Raphael Oct 18 '16 at 0:11
  • $\begingroup$ Oh, right. I just know it as cross-multiplication. So I know how to use that rule for a linear decrease in time with input. But how do I use that when there's a quadratic decrease in time with input? $\endgroup$ – learnerX Oct 18 '16 at 0:16
  • $\begingroup$ Please listen carefully: no. No, that's nothing you can do. You can do the numbers, but that doesn't make sense. It's not even wrong. See also here. $\endgroup$ – Raphael Oct 18 '16 at 0:22
1
$\begingroup$

They want you to apply rule of three under ridiculous assumptions.

If an O(n²) algorithm takes 1ms for 1000 elements, then from 1ms = c * 1000² and the ansatz Xms = c * 100000² we get that X = 10000.

In essence, they want you to assume that the running time function equals $cn^2$, in which case you could compute the constant $c$ from the given information.

The problem is that

  • $O(\_)$ is only an upper bound and does not tell you anything about the true behaviour of the described function,
  • there are unknown lower-order terms hidden in that $O(\_)$ (and also $\Theta(n^2)$, if you had that) and
  • asymptotics tell us nothing for any finite $n$.
  • They also ignore that the algorithms take different amounts of time for different inputs of the same size and
  • that "time" is a famously fickly cost measure as it depends a lot on effects like caching and process scheduling.

Therefore, the problem is senseless.

$\endgroup$
  • $\begingroup$ Thank you. I do understand that this solution is based on some big assumptions and would fail in the real-world miserably. I guess they just want to test if we understand the general concept of bit omega. $\endgroup$ – learnerX Oct 18 '16 at 0:34
  • $\begingroup$ @learnerX This problem does not test that at all! The only thing it achieves is you gaining misconceptions about Landau notation. As my first three bullets show, understanding "big oh" means understanding that the problem is ill-posed. Please, please point your teacher here. $\endgroup$ – Raphael Oct 18 '16 at 0:36

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.