Topic 1: Big O Notation and Complexity

The big O notation is easy concept, it definition is the key to solve any problem related to it.

Another topic need to understand well is the distinguish between the best case, worst case and the average case complexity of an algorithm. The following figure from Serika's book is the best illustration of the point.


We can think about running an algorithm over all possible instance of data that can be fed to it. Each of the input instance can be abstract as a point in the figure. In the figure, the x-axis represents the size of the input problem (for sorting, the number of items to sort), and the y-axis denotes the number of steps taken by the algorithm in this instance.