Hands-On High Performance with Go

O(n) – linear time

Algorithms written in linear time scale linearly with the size of their dataset. Linear time is the best possible time complexity when an entire dataset needs to be read sequentially. The amount of time an algorithm takes in linear time, scales on a 1:1 relationship with the number of items that are contained within the dataset.

Some examples of linear time are as follows:

• Simple loop
• Linear search

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

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

Note that the result computation time increases linearly and correlates to the number of items that were found in ...