David A. Tanzer, February 9, 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog.

Big O analysis

Recall our function $f(n)$ from Part 4, which gives the values 2, 13, 14, 25, 26, 37, …

Using ‘big O’ notation, we write $f(n) = O(n)$ to say that $f$ is linearly bounded.

This means that $f(n)$ will eventually become less than some linear function.

As we said, $f(n)$ has a “rough slope” of 6. So f could never be bounded by e.g. the linear function 2n. On the other hand it looks like f should be bounded by any linear function whose slope is greater than 6, e.g., $g(n) = 10n$. However, g is not a perfect bound on f, as f(0)=2 > g(0)=0, and f(1)=13 > g(1)=10.

But once $n$ reaches 2 we have that $f(n) < g(n)$.   So $f$ is eventually bounded by $g$.

Now let’s recap.

Definition.   $f(n) = O(n)$ means that for some $r > 0$ and $n_1$, we have that $n > n_1 \implies |f(n)| < r n$.

Now let’s apply big O to the analysis of this function from the previous post:

def approximately_linear(text):
    counter = 0
    for i = 1 to length(text):
        if i is odd:
            for j = 1 to 10:
                counter = counter + 1
    return counter
    

The function approximately_linear has definite linear time complexity because:

$f(n) \equiv \text{MaxSteps}(\mathit{approximately\_linear}, n) = O(n)$

Copyright © 2021, David A. Tanzer. All Rights Reserved.