Big O

Why evaluate algorithms

Two solutions to the same problem can produce the same result but behave very differently when the amount of input data becomes large. One barely notices the growth of the input, while another starts doing tens or thousands of times more work.

The Big O section is about reasoning about this in advance — without tying the analysis to a specific computer, processor, or accidental timing measurement. We will look at how an algorithm's costs grow as the size of the input data grows.

What this section covers

• Complexity Basics. We will look at what counts as input size, which operations are useful to consider, and why complexity analysis keeps the dominant behavior as the data grows.
• Time Complexity. You will learn to estimate the amount of work from the structure of the code and see how loops and repeated actions affect the growth rate.
• Space Complexity. We will look not only at time but also at the extra memory a solution needs as the input becomes larger.
• Common Complexity Classes. We will collect typical growth patterns — from almost constant work to rapidly growing algorithms — and learn to recognize them in code.
• Amortized Complexity. We will examine situations where an individual operation can occasionally be expensive, while a long sequence of such operations remains efficient on average.
• Best, Average and Worst Case. You will learn to distinguish estimates for the same algorithm on different inputs and understand which one is useful in a particular analysis.

From code to an estimate

For example, if an algorithm traverses an array once, the amount of work performed increases together with the length of the array:

int sum = 0;

for (int value : numbers) {
    sum += value;
}

In this section, we will learn to read such code not as a collection of individual lines, but as a model of how work and memory usage grow. This will become the foundation for comparing algorithms and choosing an approach before optimizing a particular implementation.