O(n)

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

The Gateway to Computer Science Excellence

+1 vote

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

$\\\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)$

0

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

+1

**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.

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

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- 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.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,291 answers

198,209 comments

104,892 users