0
$\begingroup$

How would I solve the following.

An algorithm that is $O(n^2)$ takes 10 seconds to execute on a particular computer when n=100, how long would you expect to take it when n=500?

Can anyone help me answer dis.

$\endgroup$
  • $\begingroup$ What do you think? Have you tried anything? $\endgroup$ – Juho May 4 '13 at 21:44
  • $\begingroup$ I am not sure what to do I think I have to do square rooot(500) maybe? $\endgroup$ – Fernando Martinez May 4 '13 at 21:50
0
$\begingroup$

Since it is $O(n^2)$, then $t \leq c n^2$. Therefore, since $t = 10$, and $n = 100$, $c \geq t / n^2 = 10 / 100 00$.

Therefore, at $n = 500$. You have $t \leq 10 / 100 00 \times 500^2 = 250$.

But wait, the definition of the $O$-notation claims that the above formula works for large $n$'s only. I assumed that. Although honestly, I dont like this question. It is a bet weird.

$\endgroup$
  • $\begingroup$ This answer is incorrect, you cannot use $O$ notation to predict performance like this (see @JeffE's answer). $O(n^2)$ is an upper bound for your algorithm, it only says the running time will not grow faster than some constant factor of $n^2$ as $n$ approaches infinity. $\endgroup$ – David May 6 '13 at 3:23
  • $\begingroup$ At david ... see my note in the answer $\endgroup$ – AJed May 6 '13 at 10:19
5
$\begingroup$

Formally, there is absolutely no way to tell. O( ) notation is about the limiting behavior of a function (in this case, the running time of an algorithm) as its argument (in this case, the input size) grows to infinity. Without more information, it is absolutely impossible, even in principle, to predict behavior in the limit from a finite number of function values.

$\endgroup$
  • $\begingroup$ Yet we probably do it all the time anyway, and it sort of works... For example, if transcoding 1GB of movies takes 1 minute, then transcoding 2GB will take roughly 2 minutes. $\endgroup$ – Yuval Filmus May 5 '13 at 3:32
  • 1
    $\begingroup$ @YuvalFilmus: But then you're using a more refined estimate of the running time than can be stated with O( ) notation. $\endgroup$ – JeffE May 5 '13 at 3:39

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.