1
$\begingroup$

Assuming that an implementation of a sorting algorithm takes 0,01 seconds to sort 1000 elements, how long would it take to sort 100 million elements?

What do I need to know about my the algorithm to estimate the time? Is its time complexity given in $\mathcal{O}$-notation sufficient to find that out?

In my example the algorithm is Bubblesort, of which I know that it is extremely inefficient for sorting long lists and I also know that the average case is $\mathcal{O(n^2)}$, however I am unsure how much depends on the concrete implementation, which is not given. I also am interested in the general approach towards the problem.

My train of though is that since Bubblesort is $\mathcal{O(n^2)}$ in the average case, the time cost is $c\cdot n^2$ for some constant time cost of an elementary operation $c$ (can I even assume that it is constant?). So $c \cdot 1000^2=0,01 \iff c=10^{-8}$, which would instantly give me acces for time cost for any list length $n$. I am aware that $\mathcal{O(n^2)}$ does not mean that $n^2$ is the only factor in the cost equation, but it is the leading one as $n$ grows. Is this the correct approach?

$\endgroup$
  • 1
    $\begingroup$ Why not test your ideas empirically? Instead of hypothetical rumination, you can just code it and see what happens. $\endgroup$ – Yuval Filmus Nov 25 '17 at 1:45
  • $\begingroup$ Because the implementation is not given, there can be many optimalizations made to Bubblesort which would dramatically reduce the runtime. $\endgroup$ – B.Swan Nov 25 '17 at 15:21
2
$\begingroup$

It is in general impossible to interpolate the running time of algorithms even if you know their asymptotic running time. There are many reasons for this – here are two:

  1. The running time of an algorithm is usually composed of many different terms. For example, it could be of the form $An\log n + Bn$. This running time doesn't scale like $n\log n$, since for small $n$ the $Bn$ term might be important, whereas for large $n$ it might be negligible.

  2. Resource access times do not scale in $n$, but rather jump. When $n$ is small, everything fits into the smallest cache, so data access is very quick. When $n$ gets larger, you need to use a larger cache, so all at once data access becomes slower. When $n$ gets even larger, you need to use main memory (or even beyond), and data access becomes even slower.

In some cases these reasons do not apply. For example, you might be interested in values of $n$ for which one part of the algorithm clearly takes almost all the time, and you can easily estimate how it scales in $n$; and furthermore, memory consumption is minimal so increasing $n$ doesn't result in reduced data access behavior. In such cases it is possible to extrapolate the running time.

An extreme example is when you are estimating some quantity empirically, and $n$ is the number of samples. The running time of such a program scales linearly with $n$.

$\endgroup$

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.