How does one know which notation of time complexity analysis to use?

Question Detail: 

In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity.

However, there are other notations, such as $o$, $\Omega$ and $\omega$. Are there any specific scenarios where one notation would be preferable to another?

Asked By : Jack Hunt

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/57

Answered By : Raphael

You are referring to the Landau notation. They are not different symbols for the same thing but have entirely different meanings. Which one is "preferable" depends entirely on the desired statement.

$f \in \cal{O}(g)$ means that $f$ grows at most as fast as $g$, asymptotically and up to a constant factor; think of it as a $\leq$. $f \in o(g)$ is the stricter form, i.e. $<$.

$f \in \Omega(g)$ has the symmetric meaning: $f$ grows at least as fast as $g$. $\omega$ is its stricter cousin. You can see that $f \in \Omega(g)$ is equivalent to $g \in \cal{O}(f)$.

$f \in \Theta(g)$ means that $f$ grows about as fast as $g$; formally $f \in \cal{O}(g) \cap \Omega(g)$. $f \sim g$ (asymptotic equality) is its stronger form. We often mean $\Theta$ when we use $\cal{O}$.

Note how $\cal{O}(g)$ and its siblings are function classes. It is important to be very aware of this and their precise definitions -- which can differ depending on who is talking -- when doing "arithmetics" with them.

When proving things, take care to work with your precise definition. There are many definitions for Landau symbols around (all with the same basic intuition), some of which are equivalent on some sets on functions but not on others.

Suggested reading:

• What are the rules for equals signs with big-O and little-o?
• Sorting functions by asymptotic growth
• How do O and Ω relate to worst and best case?
• Nested Big O-notation
• Definition of $\Theta$ for negative functions
• What is the meaning of $O(m+n)$?
  Is O(mn) considered "linear" or "quadratic" growth?
• Sums of Landau terms revisited
• What does big O mean as a term of an approximation ratio?
• Any other question about asymptotics and landau-notation as exercise.

If you are interested in using Landau notation in a rigorous and sound manner, you may be interested in recent work by Rutanen et al. [1]. They formulate necessary and sufficient criteria for asymptotic notation as we use them in algorithmics, show that the common definition fails to meet them and provide a (the, in fact) workable definition.

---

1. A general definition of the O-notation for algorithm analysis by K. Rutanen et al. (2015)