The most common order of algorithms is:
- Constant (O(1)): The number of steps is independent of the amount of data or it means that a constant number of steps is required, where constant can be any number not necessary just one.
2. Linear (O(n)): algorithms like the average case of the sequential search.
3. Logarithmic (O(logn)): algorithm like binary search
4. Log-linear (O(nlogn)): algorithm where the leading term is proportional to the product of the amount of data n by the algorithm of the amount of data (logn). The most efficient sorting algorithms are of this type.
5. Quadratic (O(n^2)): algorithms where the number of steps depends on the square of the amount of work that must be done. Some sorting is of this type.
Consider a situation in which we can solve a problem in three ways: one is linear, another is linear logarithmic and third is quadratic. The magnitude of their efficiency for a problem containing 10000 elements shows that the linear solution requires a fraction of second while the quadratic solution requires upto 20 minutes.
|Efficiency||Big O notation||Iterations||Estimated time|
|Linear log||O(nlogn)||140000||2 seconds|
This table contains an estimate of the time needed to solve the problem given different efficiencies.