image soruce: O'Reilly Learning
Asymptotic Analysis
Asymptotic analysis of algorithms is used to measure its time and space complexity.
So why do algorithm analysis? If we have a algorithm that runs for 1 millisecond on one computer, then we have the same algorithm run on a faster computer and it takes 1 nanosecond, does that mean the algorithm is now faster? No, we just used a faster computer. However, if we optimize the algorithm then and run it on the same computer, then we can compare the runtime as see how it performs on a more apples to apples comparison.
Time complexity deals with the amount of time an algorithm takes to run in entirety.
The amount of memory the algorithm takes
Say an algorithm is modeled by the equation 6n2, what is the big O notation? It would be n2, look at the table below for analysis
image soruce: O'Reilly Learning
| n | Algorithm model: n2 | Algorithm model: 6n2 |
| 1 | 1 | 6 |
| 2 | 4 | 24 |
| 3 | 9 | 54 |
| 4 | 16 | 96 |
| 5 | 25 | 150 |
| 6 | 36 | 216 |
| 7 | 49 | 294 |
| 8 | 64 | 384 |
| 9 | 81 | 486 |
| 10 | 100 | 600 |
| n | Algorithm model: n2 | Algorithm model: 6n2 |
| 1 | 1 | |
| 2 | 4 | |
| 3 | 9 | |
| 4 | 16 | |
| 5 | 25 | |
| 6 | 36 | |
| 7 | 49 | |
| 8 | 64 | |
| 9 | 81 |