522 views
1 votes
1 votes
g(n)=Ώ(n)

h(n)=O(n)

g(n) . h(n) =?

2 Answers

3 votes
3 votes
$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 :)
1 votes
1 votes
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.

Related questions

0 votes
0 votes
1 answer
1
Chaitanya Kale asked Nov 10, 2022
276 views
Can we write f(2$^{n/a}$) = Θ(2$^{n}$) for any integer a >0?