NOTE & BLOG

Symbols and definitions

1. Big O notation ($O$): If $\exists{c, n_{0}} \in \mathbb{R}^{+}$, such that $\forall{n} > n_0$, $f(n) \leq cg(n)$, then $f(n) = O(g(n))$.
2. Small o symbol ($o$): If $\forall{c} > 0$, $\exists{n_0}$, such that $\forall{n} > n_0$, $f(n) < cg (n)$, then $f(n) = o(g(n))$.
3. Big Omega symbol ($Ω$): If $\exists{c, n_{0}} \in \mathbb{R}^{+}$, such that $\forall{n} > n_0$, $f(n) \geq cg(n)$, then $f(n) = \Omega(g(n))$.
4. Small omega symbol ($ω$): If $\forall{c} > 0$, $\exists{n_0}$, such that $\forall{n} > n_0$, $f(n) > cg (n)$, then $f(n) = \omega(g(n))$.
5. Theta symbol ($θ$): If $\exists{c_1, c_2, n_0} \in \mathbb{R}^{+}$, such that $\forall{n} > n_0$, $c_1g( n) \leq f(n) \leq c_2g(n)$, then $f(n) = \Theta(g(n))$. It can be understood that when the complexity of the upper bound and the lower bound both increase by the same amount, then this complexity is also called a compact bound.

These notations describe the asymptotic behavior of algorithms' time complexity, aiding in understanding their performance characteristics.

Average, Best, Worst Cases

Time complexity is generally used to compare different algorithms, such as bubble sort, insertion sort, and heap sort. However, for the same algorithm, depending on the input, we can also consider average, best, and worst case time complexities. For example, the time complexity of a binary search tree varies between a singly linked list and a balanced tree.

Average Time Complexity: A measure of the weighted average of an algorithm's running time over all possible input cases. Let $T(n)$ be the running time of the algorithm for an input size of $n$. The average time complexity $\bar{T}(n)$ is defined as

$$\bar{T}(n) = \sum_{i=1}^{k} p_i \cdot T_i(n)$$

where $T_i(n)$ is the running time for the $i$th input case, $p_i$ is the probability of the $i$th case, and $k$ is the total number of possible input cases.

Best Case Time Complexity: The minimum running time required by an algorithm in the most ideal scenario.

Worst Case Time Complexity: The maximum running time required by an algorithm in the least ideal scenario.