What are Big O, Small O, Big Ω , small Ω , Small omega, Big Omega?

Question

If someone can please explain in easy words about these complexity notations? And the relation between them if there exists any? Thank you!

Answer 1

O is an asymptotic upper bound. That means if some function is O(x²), it grows *at most* as fast as x².
Ω is an asymptotic lower bound. That means if some function is Ω(x²), it grows *at least* as fast as x².
Θ is an exact asymptotic bound. That means if some function is Θ(x²), it grows *exactly* as fast as x². If something is Θ(f), then it is also at the same time O(f) and Ω(f).

It depends on what definition you are working with but in computer science we usually take big O and little o to mean the same, and big Ω and little ω to be the same aswell. In calculus, o and ω have slightly different definitions though.

To understand what "as fast as" means exactly, you'll have to plug it into the definitions you were given. Informally we scrap all the constant factors and just consider the fastest growing terms (as you've probably done before in exercises).

Also note that when CS people talk about O, they usually mean Θ, further confusing things.

Answer 2

In short, it's a measure of how the runtime of an algorithm increases as the number of inputs grows

Answer 3

Thanks, But i need a detailed answer. If professor asks me what is the difference between big oh and small o? or why the complexity of insertion sort is O(n^2) why not o(n^2) or Ω(n^2) etc.

Answer 4

This application is also part of google . if you already knew ;) and thanks for bothering to write. While i needed answer not suggessions :)