2
$\begingroup$

Θ - Tightly bound

O - Upper bound

Ω - Lower bound

I understand that for addition, the max asymptotic value is taken, for example...

if ƒ1(n) = O(n) and ƒ2(n) = O(n log n), then ƒ1 + ƒ2 = O(max(ƒ1, ƒ2) = O(n log n)

and for multiplication, the multiplied asymptotic value is taken, for example...

if ƒ1(n) = O(n) and ƒ2(n) = O(n log n), then ƒ1 * ƒ2 = O(ƒ1 * ƒ2) = O((n^2)log n)

My question is, what happens to the formulas for adding and multiplying functions of different growth rates when other bounds besides upper bounds (such as Ω - Lower bound and Θ - Tightly bound) are used?

$\endgroup$
3
$\begingroup$

Let $f(n)\in \theta(h_1(n))$ and $g(n)\in \theta(h_2(n))$.

We start with multiplication: It is easy to prove (from the basic definitions) that $f(n)\cdot g(n)\in \theta ((h_1\cdot h_2)(n))$, and similarly for $\Omega,o,\omega$.

Accordingly, multiplication of functions is preserved in all the asymptotic notations ($O,\Omega,\theta,o,\omega$)

As for addition, the idea is to make the following observation: $$f(n)+g(n)=\max\{f(n),g(n)\}+\min\{f(n),g(n)\}$$ But $\min\{f(n),g(n)\}\le \max\{f(n),g(n)\}$, so $f(n)+g(n)\le 2\max\{f(n),g(n)\}$. Thus, we get $$\max\{f(n),g(n)\}\le f(n)+g(n)\le 2\max\{f(n),g(n)\}$$

This implies that the asymptotic behavior of $f(n)+g(n)$ differs from that of $\max\{f(n),g(n)\}$ by a multiplicative constant, which means that they have the same order of magnitude, and in particular the relation is preserved under all the asymptotic notations.

To add some detail to the above, we use the observation that if e.g. $f(n)\in \Omega(h_1(n))$ and $g(n)\in \Omega(h_2(n))$, then $\max\{f(n),g(n)\}\in \Omega(\max\{h_1(n),h_2(n)\})$. This is relatively easy to prove.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.