David A. Tanzer
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 with slope 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 we say that f is eventually bounded by g.
Now let’s recap.
Definition. means that for some and , we have that .
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:
Reposted from the Signal Beat, Copyright © 2021, All Rights Reserved.
[…] David A. Tanzer, February 9, 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog. […]