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

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

Reposted from the Signal Beat, Copyright © 2021, All Rights Reserved.

One Response to Language Complexity (Part 6)

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

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.

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.