Complexity
There are different measurements of the speed of any given
algorithm. Given an input size of N, they can be
described as follows:
| Name |
Speed |
Description |
Formula |
| exponential time |
slow |
takes an amount of time proportional to a constant raised to
the Nth power |
K^N |
| polynomial time |
fast |
takes an amount of time proportional to N
raised to some constant power |
N^K |
| linear time |
faster |
takes an amount of time directly proportional to
N |
K * N |
| logarithmic time |
much faster |
takes an amount of time proportional to the logarithm of
N |
K * log(N) |
| constant time |
fastest |
takes a fixed amount of time, no matter how large the input
is |
K |