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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.
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.