Hands-On High Performance with Go

O(n2) – quadratic time

Algorithms written in quadratic time have an execution time that corresponds directly to the square of the input size. Nested loops are common quadratic time algorithms, which brings along sorting algorithms.

Some examples of quadratic time are as follows:

• Bubble Sort
• Insertion Sort
• Selection Sort

Normalized timings for quadratic time can be found in the following table:

Number of items in the dataset	Resulting computation time
10	100 seconds
100	10,000 seconds
1,000	1,000,000 seconds

You'll note from this table that as the input grows by a factor of 10, the resulting computation time grows quadratically.

Quadratic time algorithms should be avoided if possible. If you need to have a ...