Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I've noticed that Big-Oh notation actually has some properties such as summation, product but i couldn't find an introductory explanation for their use or how they can help to solve asymptotic problems.
1) Is it possible to explain these properties in plain English?
2) Can these properties be applied to Big-Omega and Big-Theta notations?
Please leave any intuitive material that can help the understanding of these properties (and others).
Thanks.
Let's start by considering the positive numbers. There is a notion of order: $$ x \leq y. $$ We can add and multiply numbers, and the order relation respect these operations: $$ x \leq y, z \leq w \Longrightarrow x + z \leq y + w, xz \leq yw. $$
Big O notation is very similar. We consider, for simplicity, functions which accept a natural number as input, and output a positive real. We define an order relation: $$ f = O(g) \text{ iff there exists } C > 0 \text{ such that } f(n) \leq Cg(n) \text{ for all } n. $$ (The funny notation $f = O(g)$ is just a notation for an order relation. Sometimes $f \ll g$ is used instead, but this is not common in computer science.)
This is similar to what we had above, with two important differences:
Since we have a function rather than a single value, we need the inequality to hold for all inputs.
We put in the extra constant $C$. This has the effect of identifying functions which differ only by a constant factor.
In more details, if $Af(n) \leq g(n) \leq Bf(n)$ for all $n$ then $g$ is "equivalent" to $f$ in the sense that $f = O(h)$ iff $g = O(h)$ and $h = O(f)$ iff $h = O(g)$.
The big O order relation also respects addition and multiplication: $$ f = O(g), h = O(k) \Longrightarrow f + h = O(g + k), fh = O(gk). $$
For positive numbers, we have not only $\leq$ but also $\geq$. These are related by $$ y \geq x \text{ iff } x \leq y. $$ The relation corresponding to $\geq$ for functions is $g = \Omega(f)$, defined by $$ y = \Omega(x) \text{ iff } x = O(y). $$ This order relation also respects addition and multiplication.
What happens if $f = O(g)$ and $f = \Omega(g)$? When this sort of situation happens in the universe of numbers, that is when $x \leq y$ and $x \geq y$, then the two numbers are equal: $x = y$. In the case of functions, we don't get equality, but rather the notion of equivalence that was mentioned above: $Af(n) \leq g(n) \leq Bf(n)$ for some positive $A,B$. In this case we write $f = \Theta(g)$.
You can think of $f = \Theta(g)$ as an analog of equality. Indeed, it is possible to quotient by this equivalence relation and work with functions "up to constant factors", but there is no need to understand this point of view when working with asymptotic notation. It suffices to understand that if $f = \Theta(g)$ then, for the most part, $f$ and $g$ are interchangeable.
(They are not interchangeable when appearing in the exponent: for example, $n^2$ and $n^3$ don't have the same asymptotic rate of growth, although $2 = \Theta(3)$. They are also not interchangeable if appearing at the base of a non-constant exponent: $2^n$ and $3^n$ have different rates of growth.)
An important special case is $Cf = \Theta(f)$ (for $C > 0$). That is, in most cases $f$ and $Cf$ are interchangeable. In other words, asymptotic notation hides constant factors. This is one of the advantages of big O notation.
Big O notation satisfies the following peculiar property: $$ f + g = \Theta(\max(f,g)). $$ This useful property allows us to simplify expressions: for example, $n^2 + n = \Theta(n^2)$. Generalizing this, if $f$ is a degree $d$ polynomial, then $f = \Theta(n^d)$.
