---
title: >-
	Big Circ notation
# katex
...

The definition of   $\bigcirc$ used by mathematicians is not convenient for engineers.

So in practice we ignore that definition and use our own.

The mathematical definition is, roughly, that if $f(n)=\bigcirc\big(g(n)\big)$ then $f(n)$ grows no faster than $g(n)$, that there exists some value K such that for values of $n$ of interest and larger than of interest $f(n)\le Kg(n)$

Which is kind of stupid for engineers, because by that definition an algorithm that takes time $\bigcirc(n)$ also takes time $\bigcirc(n^2)$, $\bigcirc(n!)$, etcetera.

So, Knuth defined $\large\Omega$, which means, roughly, that there exists some value K such that for values of $n$ of interest and larger than of interest $f(n)\ge Kg(n)$

Which is also stupid for the same reason.

So what all engineers do in practice is  use $\bigcirc$ to mean that the mathematical definition of $\bigcirc$ is true, *and*  Knuths definition of $\large\Omega$ is also largely true, so when we say that an operation take that much time, we mean that it takes no more than that much time, *and frequently takes something like that much time*.

So, by the engineer's definition of  $\bigcirc$, if an algorithm takes  $\bigcirc(n)$ time it does *not* take  $\bigcirc(n^2)$ time.

Which is why we never need to use Knuth's $\large\Omega$