sir how can be

f(n) . g(n) = Ω(n) ?

Redirected from merged question 226416

17 votes

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

- Ω (n)
- O (n)
- Ѳ (n)
- None of these

0

f(n) = theta(n) ... so we can write --> c_{1}n <= f(n) <= c_{2}n [equation 1]

g(n) = omega(n)....we can write --> g(n) >= c_{3}n [equation 2]

h(n) = O(n)....we can write --> h(n) <= c_{4}n OR -h(n) >= c_{4}n [equation 3]

Now using equation 2 nd 3

- g(n) . h(n) >= (c_{3} . c_{4})n

- g(n) . h(n) >= c_{5} n where c_{5} = c_{3} + c_{4}

g(n) . h(n) <= c_{5} n

Add eq 1 i.e f(n) <= c_{2}n to above equation

f(n) + [ g(n) . h(n) ] <= (c_{2} + c_{5})n

f(n) + g(n) - h(n) <= (c_{6})n where c_{6} = c_{2} + c_{5}

Here all c_{i} are constants.

f(n) + g(n) - h(n) = O(n) ..Hence Option a

0

what can be the Ω of this equation?

f(n) can perform Ω(1), g(n) can perform Ω(n) and h(n) can perform Ω(n)

time complexity will be Ω(n)

we cannot determine time complexity in $\Theta$ because we don't know $\Theta$ of f(n) and g(n)

f(n) can perform Ω(1), g(n) can perform Ω(n) and h(n) can perform Ω(n)

time complexity will be Ω(n)

we cannot determine time complexity in $\Theta$ because we don't know $\Theta$ of f(n) and g(n)

1

Assume:

f(n)=$n^2$

g(n)=logn

h(n)=n

f(n).g(n)=$n^2$logn

[f(n).g(n)] + h(n) ===> $n^2$logn + n ==> omega(n)

f(n)=$n^2$

g(n)=logn

h(n)=n

f(n).g(n)=$n^2$logn

[f(n).g(n)] + h(n) ===> $n^2$logn + n ==> omega(n)

25 votes

Best answer

$f(n) . g(n)$ - here the individual bounds are ≥n and ≤n respectively. So, for their product we can just say it is ≥ n or Ω(n) provided $g$ is a non-decreasing function. But $(h = \Theta(n)) \implies \left[h = O(n) \text{ AND } h = \Omega(n)\right]$.

So,$$[f(n). g(n)] + h(n) = \Omega(n).$$

(whatever be the complexity of $f(n).g(n)$, $h(n)$ grows at least at the rate of $n$ and hence the whole expression too, due to '+')

So,$$[f(n). g(n)] + h(n) = \Omega(n).$$

(whatever be the complexity of $f(n).g(n)$, $h(n)$ grows at least at the rate of $n$ and hence the whole expression too, due to '+')

0

Sir actually I am having confusion in solving such computations, I am not getting the intution of finding out what would be the result of the product ,I mean if we multiply theta(n)*omega(n) then it is equal to omega(n) acceptable but theta(n) *O(n) =O(n^2) ,couldn't get this , sorry sir but I am stucked up in such computations.

12

Solve as in numbers. I say x = 5 and y ≤ 25. Now, x * y = ? (Assume x, y ≥ 1)

We can say it is ≥ 5 and ≤ 125 rt?

We can say it is ≥ 5 and ≤ 125 rt?

2

Sir about original question, how is Ω(n)*O(n)=Ω(n) ?

we cants say anything right?

lets say n = 5, then x = 6 = Ω(n)

and y = -6 = O(n)

then x.y = -36 it is not Ω(n) right? Am I correct?

1

@Mahesha You are right. Here, I should have considered decreasing functions like $\frac{1}{n}$ which would decrease the value of functions on multiplication. Corrected now.

0

@Arjun Sir

I havenot got this line

$h = \Theta(n) \implies h = O(n) \wedge h = \Omega(n)$

Please explain

Do u mean , for every $\Theta \left ( n \right )$ and non decreasing function $\Theta \left ( n \right )=$$\Omega \left ( n \right )$

How is it possible??

8 votes

Another approach (BY TAKING EXAMPLE):-

Let $f(n) = An^2+Bn$ so $f(n)=Ω(n)$ is satisfy , $g(n) = Cn+D $ and $h(n) = En $

Now $f(n).g(n) = ( An^2+Bn).(Cn+D) = Fn^3 + Gn^2+Hn ⇒ Ω(n) $

$f(n).g(n) +h(n) = Fn^3 + Gn^2+Hn + En ⇒ Ω(n) ,O(n^3) $

OPTION A

Let $f(n) = An^2+Bn$ so $f(n)=Ω(n)$ is satisfy , $g(n) = Cn+D $ and $h(n) = En $

Now $f(n).g(n) = ( An^2+Bn).(Cn+D) = Fn^3 + Gn^2+Hn ⇒ Ω(n) $

$f(n).g(n) +h(n) = Fn^3 + Gn^2+Hn + En ⇒ Ω(n) ,O(n^3) $

OPTION A

3 votes

Let us think it a bit practically..

We know

If we have modules having time complexities T

_{1}and T_{2}, then time complexity of entire program = max(T_{1}, T_{2})

Keeping this in mind ,

Let T_{1} corresponds to f(n) and T_{2} corresponds to g(n) .h(n)..

So f(n) is guaranteed to be linear as f(n) = θ(n) ..

And g(n).h(n) if becomes larger than f(n) then the entire complexity becomes greater than function of n..It will have higher powers of n.So in that case it gives ω(n)..(Small Omega n)..

However if we have this product less than linear function of n , then we need not bother as f(n) is there to make for it..So in that complexity becomes θ(n)..

**So considering the above two cases we can say that overall complexity or in other words the function f(n) + g(n).h(n) = Ώ(n)..Hence C) is the correct answer..**

0

u say that θ(n) + ω(n) = **Ώ(n)**

* but here maximum (*θ(n) , ω(n)) = ω(n) ?? plz check

and i am not get how g(n).h(n)= ω(n) ????

0

By that I mean to say big omega is nothing but it is combination of small omega and theta..As theta gives tightest lower bound and small omega gives not tight (strict) lower bound..

But big omega simply gives lower bound..It may be tight or not tight bound..That is what I meant by that statement..

But big omega simply gives lower bound..It may be tight or not tight bound..That is what I meant by that statement..

1 vote

0

@abhishekmehta4u

We can't say for sure that complexity is O(n^2)

As g(n) is omega (n), not O(n)

When we don't know the upper bound of g(n), we can't find out the upper bound of g(n).h(n)

However, we can say that it can be omega(n) for sure, at least.

We can't say for sure that complexity is O(n^2)

As g(n) is omega (n), not O(n)

When we don't know the upper bound of g(n), we can't find out the upper bound of g(n).h(n)

However, we can say that it can be omega(n) for sure, at least.

0

can u explain the steps i am not able to understand how does u get ???

if any links available then also it will be nice !!

@abhishekmehta4u

if any links available then also it will be nice !!

@abhishekmehta4u

1

@vijju

what is the max and min value for this term [g(n)*h(n)] , min would be n as g(n) cant go below n and h(n) can become constant that case would give minimum value,

now think what can be its max value,you cant predict it

so for term [g(n)*h(n)] what you can surely say is its minimum value would be n, i.e omega(n)

now total exprsn is f(n)+[g(n)*h(n)], f(n) is theta(n) , it cant go beyond n or less than n ,so what you can say from total exprsn that value of this exprsn will always be greater or equal to n i.e omega(n)

what is the max and min value for this term [g(n)*h(n)] , min would be n as g(n) cant go below n and h(n) can become constant that case would give minimum value,

now think what can be its max value,you cant predict it

so for term [g(n)*h(n)] what you can surely say is its minimum value would be n, i.e omega(n)

now total exprsn is f(n)+[g(n)*h(n)], f(n) is theta(n) , it cant go beyond n or less than n ,so what you can say from total exprsn that value of this exprsn will always be greater or equal to n i.e omega(n)