Search code examples
algorithmtime-complexitybig-ocomplexity-theory

How do I determine if a function is Big-Omega, Big-O, or both?


Can someone give some simple example functions and explain why they're Big-Omega, Big-O, or both? Also, what does it mean for a function to be both Big-Omega and Big-O?


Solution

  • Function is not Big-Omega, or Big-O, or Big-Theta. These are all methods of understanding behavior of a function, and all three can be applied, when analyzing any function.

    Big O is an upper bound of function - so, maximum amount of memory function will use, or maximum amount of operations it needs to do before stop. Big Omega - lower bound, minimum amount of operations / memory.

    You can learn more here https://en.wikipedia.org/wiki/Big_O_notation, or just try searching for "asymptotic notation"