When we are discussing the run time of an algorithm, are we referring to big-O notation or are we saying that the runtime is the same for all cases?
For example; algorithm X runs in polynomial time.
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
4
Very rarely we measure the exact running times, and when we do, it's specified quite clearly.
Then, there is the big-O notation and its friends, which give information about the asymptotic behavior of the algorithm.
But different big-O sets (being pedant here, O(n) is actually a set of functions) can be grouped into classes. There are linear algorithms, which run in O(n). Then, there are sublinear algorithms (faster than O(n), such as O(logn)). Polynomial algorithms are quite important, and represent the algorithms with running times bounded by a polynom (e.g. O(n^k)). There are expone ntial algorithms, such as O(k^n), nonpolynomial algorithms, which grow faster than polynomial and include exponential, and so on.
All of these are simply a coarse categorization of the running time, which can be made by looking at the asymptotic behavior of the algorithm.
-
$\begingroup$ The C++ library specification actually specifies exact running times wherever possible. $\endgroup$ – Jörg W Mittag Jun 22 '19 at 20:09
-
-
$\begingroup$ For example, for
stable_sort: "Let $N$ be \tcode{last - first}. If enough extra memory is available, $N \log(N)$ comparisons. Otherwise, at most $N \log^2(N)$ comparisons. In either case, twice as many projections as the number of comparisons." $\endgroup$ – Jörg W Mittag Jun 22 '19 at 21:19 -
$\begingroup$ That is not really a running time, is the number of comparisons (not even operations). By running time I meant something like 1.5 seconds. $\endgroup$ – Paul92 Jun 22 '19 at 22:41
