The Gateway to Computer Science Excellence
+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)$
in Algorithms by Loyal (9.2k points) | 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

Theta always take leading term. 

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

@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)

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,291 answers
198,209 comments
104,892 users