Linear and Quadratic Complexity

Why be interested in complexity?

When we write an algorithm, it's important to know how much time it will take to execute and how much memory it will use.

For this, we study its complexity based on the size of data to process, which we often denote n.

Complexity gives an idea of how execution time evolves based on input size.

Linear complexity

An algorithm is said to have linear complexity when it performs a number of operations proportional to the data size.

If we double the data size, execution time also doubles.
Complexity is then expressed as O(n).

Examples:

Traversing a list to display all its elements.
Searching for an element by testing one by one (sequential search).

Quadratic complexity

An algorithm is said to have quadratic complexity when it performs a number of operations proportional to the square of the data size.

If we double the data size, execution time is multiplied by 4.
Complexity is then expressed as O(n²).

Examples:

Comparing all pairs of elements in a list (ex: naive duplicate search).
Bubble sort.

A quadratic algorithm quickly becomes very slow for large data. We therefore seek to prefer algorithms with lower complexity (linear or log-linear) when possible.