# Arithmetic of asymptotic functions

I faced some problem that involves arithmetic over asymptotic functions. These are as follows:

1. Let f(n)= Ω(n), g(n)= O(n) and h(n)= Ѳ(n). Then [f(n). g(n)] + h(n) is:

(a) $Ω(n)$
(b) $O(n)$
(c) $\Theta(n)$ (d) None of these

Solution to this was discussed as follows:

Let

• $n = 5$
• $f = 6$ so that $f = Ω(n)$ and
• $g = -6$ so that $g = O(n)$ and
• $h = 5$ so that $h = Ѳ(n)$
• $f.g + h = -36 + 5 = -31 < n → f.g + h = O(n)$

Now let,

• $g = 4$ so that $g = O(n)$ and
• $f.g + h = 24 + 5 = 29 > n → f.g + h = Ω(n)$

Hence option 4 is correct, None of these.

Then I came across another problem

1. Let $f(n)=Θ(n),g(n)=Θ(n)$ and $h(n)=Ω(n)$. Then $h(n)+f(n)g(n)= ?$

(a) $Ω(n)$ (b) $Ω(n^2)$ (c) $Θ(n)$ (d) $Θ(n^2)$

This problem was solved in completely different approach:

Using the definitions of notations:

$f(n)= θ(n)→ c_1.n<=f(n)<=c_2.n$ ... for $n>n_0$

$g(n)= θ(n)→ c_3.n<=g(n)<=c_4.n$ ... for $n>n_0$

$h(n)= Ω(n)→ h(n)>=c_5.n$ ... for $n>n_0$

Using the extended notations forms:

$c_1.c_3.n^2<=f(n)g(n)<=c_2.c_4.n^2$ ... for $n>n_0$

Taking $c_1,c_3=k_1$ and $c_2.c_4=k_3$

$k_1.n^2<=f(n)g(n)<=k_2.n^2$

$k_1.n^2+c_5.n<=h(n)+f(n).g(n)<=k_2.n^2$ ... for $n>n_0$