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).