Frequently Arising Running Times
Let's have a look at some frequently arising running times.
We'll cover the following...
Common running time complexities
The table below shows an approximate running time of four algorithms on various input sizes for a hypothetical computer that performs operations per second. The last row shows the maximum value of for which the running time of the corresponding algorithm fits into one second.
n | n log n | n2 | 2n | |
n = 20 | < 1 sec | < 1 sec | < 1 sec | < 1 sec |
n = 50 | < 1 sec | < 1 sec | < 1 sec | 13 days |
n = 102 | < 1 sec | < 1 sec | < 1 sec | 4 . 1013 years |
n = 106 | < 1 sec | < 1 sec | 17 min | - |
n = 109 | 1 sec | 30 sec | 30 years | - |
max n | 109 | 107.5 | 104.5 | 30 |
In all programming challenges in this course, your goal is to implement a program that works in at most a few seconds for all allowed input sizes ...