search
Log In
1 vote
184 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 184 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.

Related questions

0 votes
2 answers
1
152 views
O(n-1)+O(n)=O(n) O(n/2)+O(n)=O(n) but O(1)+O(2)+O(3)+...+O(n)=O(n(n+1)/2)=O(n^2) why?
asked Mar 19, 2019 in Algorithms Tanuj Guha Thakurta 152 views
1 vote
1 answer
2
54 views
Consider the following functions
asked Jun 28, 2018 in Algorithms Doley 54 views
1 vote
1 answer
3
156 views
What will be the time complexity of the following code? A() { int i,j,k,n; for(i=1;i<=n;i++) { for(j=1;j<=i;j++) { for(k=1;k<=100;k++) { printf("ABCD"); } } } }
asked Oct 20, 2017 in Algorithms Manish Chetwani 156 views
2 votes
1 answer
4
216 views
Find the time complexity of the following recurrance relation: T(n) = T(n - 1) + sin(n) , 'n' is measured in degree(s) Options are: A) $theta$(n) B) $theta$(1) C) $theta$(logn) D) $theta$(n.logn)
asked Nov 8, 2016 in Algorithms Sushant Gokhale 216 views
...