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:

Note that the result computation time increases linearly and correlates to the number of items that were found in our dataset (refer to the following screenshot). The code and benchmark of an O(n) function can be found at https://github.com/bobstrecansky/HighPerformanceWithGo/tree/master/2-data-structures-and-algorithms/BigO-notation-o-n:

An important point to remember is that Big O notation isn't necessarily a perfect indicator of response time growth; it just denotes an upper ceiling. While reviewing this benchmark, focus on the fact that the resulting computation time grows linearly with the number of items in the dataset. O(n) algorithms are typically not the big showstopper in computer science from a performance perspective. Computer scientists perform loops on iterators frequently, and it's a common pattern that's used to get computational work completed. Make sure that you're always cognizant of the size of your dataset!