Performance Analysis

Why analyze algorithms?

Suppose two algorithms solve the same problem. One performs 1,000 operations, the other performs 1,000,000. For a small input, that difference is barely noticeable. For a large input, it can mean the difference between a program finishing instantly and one that takes minutes.

The real question behind analyzing an algorithm is: how much time and memory does it require as the input size grows?

Other factors like network usage or battery/power consumption can matter in specific contexts, for example on a mobile app or an embedded device, but time and memory are the two that scale with input size and affect every program regardless of where it runs. That is why they are the standard measures used to compare algorithms.

This leads to performance analysis: studying an algorithm's cost along these two independent dimensions.

Time complexity asks how the number of operations grows with input size. Space complexity asks the same question about memory. An algorithm can be fast but memory-hungry, or slow but memory-light, so both are analyzed separately rather than folded into a single score.

Quick recall

• Performance analysis studies an algorithm along two independent axes: time and memory.
• Time and memory are the standard measures because they scale with input size and apply to every program.
• The next two topics, Time Complexity and Space Complexity, cover each axis in detail.