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