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

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?

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

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

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

StackExchange Computer Science Q#57, answer score: 86