40 Algorithms Every Programmer Should Know

Quadratic time (O(n2)) complexity

An algorithm is said to run in quadratic time if the execution time of an algorithm is proportional to the square of the input size; for example, a simple function that sums up a two-dimensional array, as follows:

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

Note the nested inner loop within the other main loop. This nested loop gives the preceding code the complexity of O(n²):

Another example is the bubble sort algorithm (as discussed in Chapter 2, Data Structures Used in Algorithms).