Algorithm Complexity

Big-O Notation

• 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