+1 vote
85 views
Kindly verify these and provide answer to others-

$\\\Theta (n).O(n) = ?\\ \Theta (n).\Omega (n) = \Omega (n)\\ O(n).\Omega (n) = \Omega (n)\text{when function is non decreasing and what if it is decreasing?}\\ \Omega (n)+\Theta (n) =\Omega (n)\\ O(n)+\Theta (n) = ?\\ O(n)+\Omega (n)=\Theta (n)$
| 85 views
0
O(n*n)

O(n)

i think last one should not be theta of n we can say only Omega(n)
0

@Abhisek Tiwari 4, I think first one is correct but can you please give explanation for fourth one and last one?

+1

@Shubhgupta

same reason for both

.>>>>>.e.g linear serach and Insertion sor O(n) + omega(n) but not theta(n) because avg case of insertion sor n*n.

0
correct me if i am wrong for last statement

f= O(n), g=$\Omega (n)$

so we know that f(n)<=c.n and g(n)>=c.n

so suppose if x<=5 and y>=5.. so we can say that x+y>5 when f(n) is non decreasing function so it will be $\Omega (n)$ right? but what if it f(n) is decreasing function then we can not conclude that x+y will be $\Omega (n)$

like ex- x=-10 and y=5 then x+y = -5 then in this what we can conclude?

Thanks for your help brother! but it is confusing me a lot.
0
if 2nd part decreasing function mentioned  then i think   O(n) should be answer.
0

@Shaik Masthan

Can you help in this ..how to solve such questions ?

By just taking examples it sometimes go wrong

0

Θ(n).O(n)  = (exactly n) . (≥n) = ≥n$^2$ ===> O(n$^2$)

O(n)+Ω(n)=Θ(n)

it doesn't mean, Function F takes O(n) and Ω(n)

it means, Function F$_1$ takes O(n) and F$_2$ takes Ω(n) then overall is O(n)

Ω(n)+Θ(n)=Ω(n)

more appropriate is Θ(n) due to it is dominating Ω(n).

check remaining also...

0

@Shaik Masthan, Thanks for checking..:)

Ω(n)+Θ(n)=Ω(n)

more appropriate is Θ(n) due to it is dominating Ω(n).

I don't think we can conclude that it will be Θ(n). a simple interpretation is  x>5 and y=5 then x+y should be greater than 5. Right?

Moreover where function is O(n) then it depends on that function whether it is increasing or decreasing.

Correct me if anything wrong?

0

I don't think we can conclude that it will be Θ(n). a simple interpretation is  x>5 and y=5 then x+y should be greater than 5. Right?

you are taking integers here, but take in terms of n, then you will get what i want to say !

but don't forget, $n^2 + n + 1$ = Θ(n)

0
0

@Shubhgupta

ya, i did wrong, Thanks for correcting me !

i assumed f(n) = O(n) means f(n) ≥ n, but actually it is f(n) ≤ n.

But the process is same, like

Θ(n).O(n)  = (exactly n) . (≥n) = ≥n$^2$

===> O(n$^2$)

Θ(n).O(n)  = (exactly n) . (n) that is equal to  n$^2$

===> O(n$^2$)

Ω(n)+Θ(n)= ( ≥ n ) + ( exactly n ) = ( minimum n ) = Ω(n)