Arithmetic of asymptotic functions

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



-
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

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



-
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.nn_0$

$g(n)= θ(n)→ c_3.nn_0$

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

Using the extended notations forms:

$c_1.c_3.n^2n_0$

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

$k_1.n^2n_0$

As $n^2>n$ for all $

$k_3.n^2<=h(n)+f(n).g(n)<=k_2.n^2$

Which simplifies to :

$f(n).g(n) + h(n) =Ω(n^2)$

Though I am able to appreciate both approaches, this leaves me a lot of confusion. I am not able to confidently apply these methods to each other, nor to other similar problems and reach the correct solution. Are these methods correct? In fact are these questions themselves correct? Is there more straightforward approach to solve such kind of problems?

One way to help understand what's going on conceptually would be to draw a linear graph of what each of these functions mean.

So for example, say we're given a problem that tells us:

$g_1(n)=\Theta(lg(n))$

$g_2(n)=O(n^2)$

$g_3(n)=\Omega(n)$

we can make a quick sketch of where they could be in relation to each other.

With this visual, we can get an idea of possible candidates for these functions.

So let's bring it back to one of the questions you had trouble understanding:


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

We know that $f(n)$ and $g(n)$ are both tightly bounded at $n$, so if you multiply them together, you'll clearly get $\Theta(n^2)$.

Now if we also add some function $h(n)$ that we know has a lower bound of $n$, the result must be $\Theta(n^2)+\Omega(n)$ which we can reduce to $\Omega(n^2)$, since an additional $...+\Omega(n)$ factor will be at its lowest value $n$ but there is no bound on how high this function can be (it could be anywhere from $n$ to $n^{1000}$ since there's no telling what an upper bound is), so we can conclude that it's $\Theta(n^2)+n=\Omega(n^2)$

StackExchange Computer Science Q#57157, answer score: 2