[Solved]: Behavior of different multiplied and added time complexities

Problem Detail: 

Θ - 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?

Asked By : Ogen

Answered By : Shaull

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12685

3.2K people like this

 Download Related Notes/Documents