Asymptotic notations

Question

g(n)=Ώ(n)

h(n)=O(n)

g(n) . h(n) =?

Comments

g(n).h(n) = $\Omega$ (n). I don't think there is any upper bound for this.

---

Can you explain a bit?

I am unable to get it logically.How this is possible ?

Why it is not O(n^2) ?

Answer 1

$g(n).h(n)$ will be $\Omega (n)$

Since, we know that $g(n) = \Omega (n)$, so it can be any function which is asymptotically greater than or equal to n,

i.e $g(n) \geq  c_{1}n$.

And, $h(n) = O(n)$, i.e. $h(n)$ can be any function which is asymptotically less than or equal to n,

i.e. $h(n) \leq c_{2}n$.

When we multiply both these functions, we can only conclude that it will be $\Omega (n)$.

Because $h(n)$ can possibly be $O(1)$.

And since there is no upper bound on $g(n)$, so we cannot put any upper bound on $g(n)h(n)$.

Hope that helps :)

Comments

yes there is no upeer bound for this

---

Nice explanation :)
I have a small doubt :

We know that

if f(n)=O(g(n)) and

d(n)=O(e(n))

then

1) f(n) / d(n) = O(g(n))

if d(n) is increasing function

I am not clear about the significance of increasing function , can u explain a bit ?

PS: Not related to this question but I have a general doubt.

---

I am also not sure about this.

Increasing function means, with the increase in the value of n, f(n) will also increase. And in algorithms point of view, we always have increasing functions, since with increase in input size, the time it takes will also increase.

Some examples of functions that are NOT increasing are f(n) = 1/n.

P.S. I am also not sure if it is correct or not.

Answer 2

I am taking few examples so that my explanation becomes easy consider the given examples:-

Example 1: let g(n)=n^2, h(n)=n

so from first equation says g(n)=Ώ(n) i.e., n^2>=c1.n which is true for this example.

second equation says  h(n)=O(n) i.e., n<=c2.n which is true again

g(n).h(n)=n^3=Ώ(n)

Now consider second example

Example 2:: let g(n)=n^2, h(n)=1

second equation says  h(n)=O(n) i.e., 1<=c2.n which is true again

g(n).h(n)=n^2=Ώ(n) //Because of equal to

 

Hence from the above 2 examples we can conclude that g(n).h(n)=Ώ(n) means upper bound is not be possible at all.