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.
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 communityWhen 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.
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.
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