- Big-O refers as $O(n)$.
- It use to mean either the time complexity of an algorithm (called time complexity) or how much ram it can consume during the process (called as auxiliary space).
- Definition: Suppose $f(x)$ and $g(x)$ are two functions defined on some subset of the real numbers. We write $f(x) = O(g(x))$ for $x \to \infty$ iff $\exist$ constants $N$ and $C$ such that $|f(x)| \leq C |g(x)|~\forall~x > N$.
- The above definition suggests $f(x)$ does not grow faster than $g(x)$.
- Idea: To calculate $O(n)$, identify the worst case for the targeted algorithm and formulate a function of its performance given an $n$ amount of elements.
- Example: If we have an algorithm that search for the number 7 in an array, then the worst case scenario would be if 7 is at the end of the array. This means our time complexity is linear that is of order $n$ $O(n)$, and suggest us that the algorithm need to run through the entire $n$-element array before finding the number 7.
Table with algorithms and complexity
Published on Jul 13, 2021
Last revised on Jul 13, 2021