notating algorithm running time

Let’s say we have an algorithm runtime function $f(n)$. $f(n)$ can be a runtime function for worst, average, or best case scenario; note that these three scenarios may require different runtime functions. We can describe $f(n)$ with an approximation function $g(n)$ like so (in order of upper to lower bounds):

• $f(n)=o(g(n))$: little-o notation
  • $g$ is an asymptotic upper bound that is strictly not asymptotically tight
  • algorithm runtime grows no faster than $g$
• $f(n)=O(g(n))$: big-O notation
  • $g$ is an asymptotic upper bound that is not necessarily tight
  • algorithm runtime grows no faster than $g$
• $f(n)=\Theta (g(n))$: big-Theta notation
  • $g$ is an asymptotic tight bound
  • algorithm runtime grows as fast as $g$
  • exists only if big-O and big-Omega is within a constant factor of each other
• $f(n)=\Omega (g(n))$: big-Omega notation
  • $g$ is an asymptotic lower bound that is not necessarily tight
  • algorithm runtime grows faster than $g$
• $f(n)=\omega (g(n))$: little-omega notation
  • $g$ is an asymptotic lower bound that is strictly not asymptotically tight
  • algorithm runtime grows faster than $g$

Why don't constant coefficients matter?

The reason why coefficients don’t matter is because the way these notations are defined throws the constants out of the window anyway (e.g. $\Theta (n)=\Theta (3n)=\Theta (0.1n))$. However, the coefficients (and other lower-degree polynomial terms) should still be taken into account when choosing an algorithm in real life, as the $n$ may not always be large enough for us to consider the asymptotic behavior.

Why do we use equal signs?

These equalities are not really equalities. It is easier to think of them as set memberships. For instance, $f(n)=\Theta (g(n))$ means that $f(n)$ belongs to the set of functions that grows as fast as $g(n)$.

The reason why equal sign is used is due to its convenience in cases like $e^x+O(x)=O(e^x)$ where asymptotic notation appears on both sides, and also $\sin x=x-\frac{x^3}{3}+O(x^5)$ where the equal signs mean there is an $O(x^5)$ function satisfies the equality (source).

Does big-O mean worst case?

Big-O doesn’t necessarily mean worst case, and big-Theta doesn’t always mean average case. You can use big-Theta to precisely describe the worst case runtime of an algorithm, and you can also use big-O to estimate what the average runtime would be for an algorithm. See here for more explanation.

Be careful when comparing big-O notations

$f(n)=\Theta (n)$ can count as $O(n)$ and $O(n^2)$, but it only has one big-theta notation. The big-theta notation most closely reflects the growth of the function because it requires a tight bound. In other words, while $O(g(n))$ and $\Omega (h(n))$ can represents the growth of a function, they don’t have to, e.g. the $f(n)$ might be $O(n\log n)$ but you can also say it’s $O(n^2)$: technically not wrong, but quite off. When comparing the big-O notations of two functions, take care in determining how tight the bound is.