Can you do addition/multiplication with Big O notations?

Question

I'm currently taking an algorithm class, and we're covering Big O notations and such. Last time, we talked about how

O (n^2 + 3n + 5) = O(n^2)

And I was wondering, if the same rules apply to this:

O(n^2) + O(3n) + O(5) = O(n^2)

Also, do the following notations hold ?

O(n^2) + n

or

O(n^2) + Θ (3n+5)

The later n is outside of O, so I'm not sure what it should mean. And in the second notation, I'm adding O and Θ .

Answer 1

At least for practical purposes, the Landau O(...) can be viewed as a function (hence the appeal of its notation). This function has properties for standard operations, for example:

O(f(x)) + O(g(x)) = O(f(x) + g(x))
O(f(x)) * O(g(x)) = O(f(x) * g(x))
O(k*f(x)) = O(f(x))

for well defined functions f(x) and g(x), and some constant k.

Thus, for your examples,

Yes: O(n^2) + O(3n) + O(5) = O(n^2)
and:
O(n^2) + n = O(n^2) + O(n) = O(n^2),
O(n^2) + Θ(3n+5) = O(n^2) + O(3n+5) = O(n^2)