The Big Oh notation (O, Theta, Omega) is about growth rates of functions.

When you implement an algorithm, it has a certain characteristic how the runtime changes when you increase the dataset operates on. Now, you may optimize the algorithm so it runs faster by a factor of 100. Sure, this is great, but essentially, it’s still the same algorithm. Similarly, in a few years, computers may be twice as fast as they are today.

The Landau notation abstracts away these constant factors. It doesn’t care about whether an algorithm f is always twice as fast as another algorithm g: Maybe g can be optimized to run 4 times faster, or you might be able to buy faster hardware instead. If you look at it from this perspective, you might say they are “the same”. (That is not to say you can (always) ignore constant factors in practice.)

Big oh specifies an upper bound, it’s similar to the <= relation.

You will agree that 1 < 2 is true. Does that mean that 1 cannot be less than any other number? Certainly not. There is an infinite amount of numbers that are bigger than 1.

With growth rates, it’s similar. O(n) denotes the set of all functions, that grow linearly (or more slowly). O(n^2) on the other hand denotes all those functions, that grow with quadratic compelxity (or slower). I am sure that you will agree that a linear function grows more slowly than a quadratic function.

This is why a function can be in more than one “Big-oh” class.

Here is a comparison of different functions with : (from Knuth’s Concrete mathematics)

From left to right, functions grow faster.

Also, , meaning n^2 grows faster than n^1 because 2 > 1.

Definitions

“f grows faster or equally fast as g”

“f grows slower or equally fast as g”

The combination of the above two. It says the function f grows “equally fast” as g. It’s an equivalence relation.

Interpretation

Let’s say you have two algorithms, f and g.

Omega

Assuming , means that no matter your budget, there is no constant amount of computing power that you can add to your system, such that f will always run as fast as g.

Big oh

Assuming , means that if you have enough data, f will always run faster than g, no matter how much computing power you add to your system.

Proof

If you are really trying to prove this, you need to show using the definitions of the Landau notation that your function satisfies the necessary conditions.

So you need to find values for c, d, n_0 such that the condition holds.

Here is how you can do that for the lower bound with c:

It is important to realize, that me arbitrarily defining c as being smaller than a-1 is perfectly fine. The definition of Theta(g) says that “there exists a c“. It can be any value as long as it is bigger than 0. (If a is a positive real number, you would need to change the proof slightly however, because a - 1 might actually be negative)

(I am assuming a to be positive, otherwise the function will always be negative for big values of n, which makes no sense for a function denoting the runtime.)

You can try doing it for the upper bound, it’s quite similar. If you don’t know how, I can provide a proof for you.

Hint: start with d > a + 1

Attention

It is important that you do not prove it the wrong way around. If you assume that (an + b) is in O(n) and go from there, you have not proven what you wanted. You will need to verify that all of your steps go both way, i.e. instead of => you have <=>.

When you’re dealing with polynomials, you only care about the degree of the polynomial. That is, for an + b, you only care about n. If it was an^3 + bn^2 + cn + d, you would only care about n^3.

So a polynomial with degree d will always be in Θ(n^d). Simple.

Now we need to talk about the difference between Θ and O. Essentially, it’s the same difference as between == and <= respectively. So Θ(n) means that it is always within a constant factor of n. O(n) means that it is always either within a constant factor of n or less than n.

This means that any function in Θ(s), for any s, will also be in O(s). Also, if a function is in Θ(s) and s is always less than some other function t, that function is in O(t) but not Θ(t).

For the sake of completeness, there is also Ω(n). If Θ represents == and O represents <=, Ω represents >=. So an + b is in Ω(1), Θ(n) and O(n^2).

As I said earlier, it’s really easy to figure out what class polynomials are in–you just look at the degree. There are some other functions that are easy to work with as well.

Any functions in the form of a^bn for arbitrary a and b are in Θ(a^n). For any value c >= a, they are in O(c^n). Every polynomial is in O(2^n). Essentially this just says that exponential functions always beat out polynomials and that the base of the exponential function matters.

Logarithms are the opposite. For one, log_b n is in Θ(log n) for any b. This means the base doesn’t matter for logarithms. This makes sense because switching between different bases in logarithms is just multiplying by a constant. Logarithmic functions are also in O(n)–that is, a logarithmic function is smaller than any polynomial (at least of degree 1).

Given a sum of these functions, the biggest one “wins”. So n + log n is in Θ(n) because the n term dominates the log n term. Multiplication is more complicated. For CS, the only thing you need to know is that nlog n is between n and n^2.

Without using much math, you take the function f(n)= an+b and drop all the constants, so it looks like this f(n)= n, then you take the “n” with the highest degree as your answer
Q.E.D Θ(n)