Technically, we analysed an implementation of the algorithm; perhaps a cleverer implementation could be more efficient. From one perspective, the implementation is what we really care about:
- The implementation is what will actually be run in the real world.
- A more efficient implementation will make a real piece of software faster.
On the other hand, it’s hard to do an accurate dynamic analysis:
- There will always be some measurement error.
- It might take a long time to do the analysis.
- Running time depends on external factors like how fast the computer is, or what other programs are running. Results from different computers, or even the same computer on different days, may be incomparable.
In this post, we’ll get around these problems by making a series of simplifications. We’ll do a kind of static analysis called asymptotic analysis — this means we’ll analyse algorithms without running them, and we’ll assume the inputs are large.