CODEWITHSUNDEEP
algorithmdata-structurescomputer-science
karahbit
karahbit

Reputation: 93

Can we estimate Big Omega just like we do with Big O?

I keep reading how easy it is to estimate Big O: drop least dominant terms and constants. My question is, can we do the same for Big Omega?

I know input dependency has nothing to do with asymptotic analysis: we can have an upper (Big O) and lower (Big Omega) on best, average and worst case analysis. But I am confused on how I can quickly estimate Big Omega of my algorithm, in the worst case for example.

If you could provide examples to clarify my confusion I would truly appreciate it.

Upvotes: 1

Views: 62

Answers (1)

user1196549
user1196549

Reputation:

Just two examples should enlighten you.

n² + n is O(n²) (it is also O(n³)).

n² + n is Ω(n²) (it is also Ω(n)).

You consider the dominant term.

n + (n cos n)² is O(n²) and Ω(n).

Upper and lower bound.

Upvotes: 1

Related Questions