David A. Tanzer
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 suboptimal implementation, the number of steps is proportional to the square of the size of the input.
This says that f becomes eventually bounded by some quadratic function. On the other hand, it is not the case that , as will eventually exceed any linear function.
Here is the general definition of big O notation:
Definition. means that for some and , we have that .
Any function which is eventually bounded by a linear function must also be eventually bounded by a quadratic function, i.e., linear functions are “smaller than” quadratic functions. So makes a stronger statement than . Generally, we try to make the strongest statement possible about the complexity of a function.
Reposted from the Signal Beat, Copyright © 2021, All Rights Reserved.