# 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

Permalink athttps://www.physicslog.com/cs-notes/algorithm-complexity

Published onJul 13, 2021

Last revised onJul 13, 2021