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$
2
  • $\begingroup$ What do you think? Have you tried anything? $\endgroup$
    – Juho
    May 4, 2013 at 21:44
  • $\begingroup$ I am not sure what to do I think I have to do square rooot(500) maybe? $\endgroup$ May 4, 2013 at 21:50

2 Answers 2

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$
2
  • $\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, 2013 at 3:23
  • $\begingroup$ At david ... see my note in the answer $\endgroup$
    – AJed
    May 6, 2013 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$
2
  • $\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$ May 5, 2013 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, 2013 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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