40 Algorithms Every Programmer Should Know

Linear time (O(n)) complexity

An algorithm is said to have a complexity of linear time, represented by O(n), if the execution time is directly proportional to the size of the input. A simple example is to add the elements in a single-dimensional data structure:

def getSum(myList):    sum = 0    for item in myList:        sum = sum + item    return sum

Note the main loop of the algorithm. The number of iterations in the main loop increases linearly with an increasing value of n, producing an O(n) complexity in the following figure:

Some other examples of array operations are as follows:

• Searching an element

• Finding the minimum value among all the elements ...