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 .

Then .

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.

This entry was posted on Thursday, March 18th, 2021 at 7:01 am and is filed under computer science. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it. Cancel reply

You need the word 'latex' right after the first dollar sign, and it needs a space after it. Double dollar signs don't work, and other limitations apply, some described here. You can't preview comments here, but I'm happy to fix errors.

[…] David A. Tanzer, February 10, 2021, in course Language Complexity. Cross-posted to the Azimuth Blog. […]