DS&A

Data Structures and Algorithms

Static Analysis

May 072018

In the previous post we analysed how efficient the insertion sort algorithm is. We did dynamic analysis — we analysed the algorithm by actually running it.

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.

‘Big O’ Notation

May 072018

By making a series of assumptions and considering only “large” inputs, we can analyse how efficient an algorithm is without actually running it. The result of this analysis is a mathematical formula called the complexity (or time complexity) of the algorithm. For example, we derived the formula n2 for the selection sort algorithm.

Using standard notation, we would say that selection sort’s complexity is O(n2), or that selection sort is an O(n2) algorithm.

This formula says, very roughly, how much “work” the algorithm has to do as a function of n, which represents the “input size”. In this post, we’ll see how to make sense of this formula, and how to derive it with as little algebra as possible.

Atom

hosted on werp.site