:PROPERTIES: :ID: b52fee3e-988c-4ca9-ab9e-e9f036e7e525 :mtime: 20231009024247 :ctime: 20231009024159 :END: #+title: Big O Notation #+filetags: :public:project: * Defintiion We write $f(n) = O(g(n))$ if there exists a $c$ such that for all $n$, $f(n) \le c g(n)$. * Examples - $O(2g(n)) = O(g(n))$ - $O(\log_{10} n) = O(\ln n)$ - $O(n^2 + 50n + 36) = O(n^{2})$ * Names of Complexity Classes The classes each have names | Big O | name | |--------------+-------------| | $O(1)$ | constant | | $O(\log n)$ | logarithmic | | $O(n)$ | linear | | $O(n \log n$ | quasilinear | | $O(n^2)$ | quadratic | | $O(n^{3})$ | cubic | | $O(e^n)$ | exponential |