Big O Algebra simplify

Question

To simplify a big O expression

1. We omit all constants
2. We ignore lower powers of n

For example:

O(n + 5) = O(n)

O(n² + 6n + 7) = O(n²)

O(6n1/3 + n1/2 + 7) = O(n1/2)

Am I right in these examples?

Answer 1

1. We omit all constants

Well, strictly speaking, you don't omit all constants, only the outermost multiplicaive constant. That means O(cf(n)) = O(f(n)). Additive constants are fine too, since f(n) < f(n)+c < 2f(n) starting with some n, therefore O(f(n)+c) = O(f(n)).

But you don't omit constants inside composite functions. Might be done sometimes (O(log(cn)) or even O(log(n^c)) for instance), but not in general. Consider for example 2^2n, it might be tempting to drop the 2 and put this in O(2^n), which is wrong.

2. We ignore lower powers of n

True, but remember, you don't always work with polynomial functions. You can generally ignore any added asymptotically lower functions. Say you have f(n) and g(n), when g(n) = O(f(n)), then O(f(n) + g(n)) = O(f(n)).

You cannot do this with multiplication.

Answer 2

You're almost right. The second rule should be that you ignore all but the term with the largest limit as n goes towards infinity. That's important if you have terms that are not powers of n, like logs or other mathematical functions.

It's also worth being aware that big O notation sometimes covers up important other details. An algorithm that is O(n log n) will have better performance than one that is O(n^2), but only if the input is large enough for those most terms to dominate the running time. It may be that for the sizes inputs you actually have to deal with in a specific application, the O(n^2) algorithm actually performs better!