Redirected
in Algorithms
18,427 views
21 votes
21 votes

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

  1. Ω (n)
  2. O (n)
  3. Ѳ (n)
  4. None of these
in Algorithms
18.4k views

4 Comments

Any process without any assumptions?
0
0
how did you assume f(n) is Ω(1)  and h(n) is Ω(n)?
0
0

7 Answers

26 votes
26 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 '+')
edited by
by

4 Comments

How??

$\Theta$ is stronger notation than $O.$ and $\Theta$ is asymptotically tight bound. Then how can we say

$O\wedge \Theta =\Omega$ ??
0
0
got it :)
1
1
Sir, I just wanted to confirm what I have understood from all the above conversation. Plz let me know if all below statements are correct or not.

We can write :
O(n) as f(n) <= n

Ω(n) as f(n) >= n

Φ(n) as f(n) = n

Is this all correct ?
0
0
8 votes
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

1 comment

nice approach sir
0
0
3 votes
3 votes

Let us think it a bit practically..

We know

If we have modules having time complexities T1 and T2 , then time complexity of entire program = max(T1 , T2)

Keeping this in mind ,

Let T1 corresponds to f(n) and T2 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..

2 Comments

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
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..
0
0
2 votes
2 votes

..............

3 Comments

@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.
0
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
0
0
@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)
1
1
Answer:

Related questions

0 votes
0 votes
2 answers
3