Excursion: Algorithm Analysis

This lesson introduces the concept of big-O\mathcal{O}-notation for describing the worst-case runtime of an algorithm. If you are already familiar with big-O\mathcal{O}-notation, feel free to skip this lesson.

Counting operations

Computer science problems can be solved with various different algorithms. Naturally, this leads to the task of comparing different algorithms for the same problem to find out which one is the best. More often than not, this boils down to the question “which algorithm is the fastest?”

To measure and compare the runtime behavior of algorithms, we can count the number of operations that the algorithm must perform compared to the size of its input. For illustration, consider the following C++-function that checks whether there are two elements in a vector that sum to zero.

Get hands-on with 1200+ tech skills courses.