David A. Tanzer, February 10, 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog.
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 suboptimal implementation, the number of steps is proportional to the square of the size of the input.
Let $f(n) = MaxSteps(\mathit{square\_length}, n)$.
Then $f(n) = O(n^2)$.
This says that f becomes eventually bounded by some quadratic function. On the other hand, it is not the case that $f(n) = O(n)$, as $f(n)$ will eventually exceed any linear function.
Here is the general definition of big O notation:
Definition. $f(n) = O(g(n))$ means that for some $r > 0$ and $n_1$, we have that $n > n_1 \implies |f(n)| < r g(n)$.
Note that any function which is eventually bounded by a linear function must also be eventually bounded by a quadratic function — since linear functions are “smaller than” quadratic functions. This means that $f(n) = O(n)$ makes a stronger statement than $f(n) = O(n^2)$. Generally, we try to make the strongest statement possible about the complexity of a function.
Copyright © 2021, David A. Tanzer, All Rights Reserved.
