sir how can be

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

The Gateway to Computer Science Excellence

+15 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

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)

+22 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.

+11

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??

+5 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..

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,666 questions

56,159 answers

193,767 comments

93,762 users