Scenario
We have been asked to develop a timing table using an input size of 2, 10, 30, and 50 for an exponential algorithm of O(2n). Assume an operation time of 0.5 ms and that the algorithm only performs one operation.
Aim
To discover how badly exponential algorithms scale.
Steps for Completion
- 0.5 x 22 = 2 ms
- 0.5 x 210 = 512 ms
- 0.5 x 230 = 0.536 billion ms = 6.2 days
- 0.5 x 250 = 5.629 and 1014 ms = 17838 years
Output
The results may be as follows:
| Input Size (n) | Time : 1 Operations O(2n) |
| 2 | 2 milliseconds |
| 10 | 512 milliseconds |
| 30 | 6.2 days |
| 50 | 17838 years |
In this section, we have compared different types of algorithmic runtime complexities. We have seen how each compares against the others, starting from the theory's fastest of O(1) to some of the slowest with O(kn). It's also important to understand that there is a diļ¬erence between theory and practice. For example, in real life, a quadratic algorithm may outperform a linear one if the operations performed are less, the input is a fixed size, and is small.