Language Complexity (Part 6)

David A. Tanzer

Quadratic complexity

In Part 5 we introduced big O notation for describing linear complexity. Now let’s look at a function with greater than linear complexity:

def square_length(text): # compute the square of the length of text # FIXME: not the most elegant or efficient approach n = length(text) counter = 0 for i = 1 to n: for j = 1 to n: counter = counter + 1 return counter

Here, due to the s...