We can represent a linear algorithm (one where the number of steps
increases in direct proportion to the amount of data) by the notation
O(n), which read order of ‘n’. This notation means that for large value
of n (where n is quantity that measures the amount of data being
processed by the algorithm), the no. of steps taken by the algorithm is
directly proportional to the amount of data being processed. So, all the
algorithms can be classified by giving their order in the form of big
‘O’ notation. To do this, we must find an expression for the dependent
of the number of steps in the algorithm on the amount of data being
processed.
The most common order of algorithms is:
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.
This table contains an estimate of the time needed to solve the problem given different efficiencies.
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 |
| Logarithmic | O(logn) | 14 | microseconds |
| Linear | O(n) | 10000 | 0.1 seconds |
| Linear log | O(nlogn) | 140000 | 2 seconds |
| Quadratic | O(n^2) | 10000^2 | 15-20 minutes |
| Polynomial | O(n^k) | 10000^k | hours |
| Exponential | O(c^n) | 2^10000 | Intractable |
| Factorial | O(n!) | 10000! | Intractable |
This table contains an estimate of the time needed to solve the problem given different efficiencies.
No comments:
Post a Comment