Big Oh Notation

formal definition

complexity analysis

algorithm efficiency

computational theory

Big Oh Notation - formal definition

Master System Design with Codemia

Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.

Big Oh Notation, also known as Big O notation, is a mathematical notation used to describe the upper bound of the time complexity (or space complexity) of an algorithm. It is a crucial concept in computer science for analyzing and comparing the efficiency of algorithms. Here, we'll delve into its formal definition and practical significance.

Formal Definition

Big Oh Notation is formally defined in terms of functions. Suppose $ T(n) $ and $ f(n) $ are functions where $n$ typically represents the size of the input. We say:

$T(n) = O(f(n))$

if there exist positive constants $ c $ and $ n_0 $ such that:

$0 \leq T(n) \leq c \cdot f(n)$

for all $n \geq n_0$ .

This definition essentially means that for sufficiently large input sizes, the growth of $T(n)$ is bounded above by a constant factor of $f(n)$ .

Technical Explanation and Examples

Example 1: Linear Time Complexity

Consider a simple algorithm that calculates the sum of elements in an array of size $n$ . The time complexity of this algorithm can be expressed as $T(n) = cn + d$ , where $ c $ and $ d $ are constants representing the time to process each element and the setup overhead, respectively.

To express this in Big O notation, observe that for large $n$ , the $cn$ term dominates the behavior of $T(n)$ . So, we can say:

$T(n) = O(n)$

Example 2: Quadratic Time Complexity

Consider a nested loop algorithm where for every element of the input, we perform a linear scan. This results in a time complexity of $T(n) = an^2 + bn + c$ .

Applying the definition of Big Oh, we find:

$T(n) = O(n^2)$

because the quadratic term dominates as $n$ grows larger.

Example 3: Logarithmic vs. Linearithmic Complexity

Algorithms like binary search operate in logarithmic time, formally written as $O(\log n)$ , while sorting algorithms like Merge Sort operate in $O(n \log n)$ . Here are examples of relevant functions and their Big O notation:

Binary Search: $T(n) = O(\log n)$
Merge Sort: $T(n) = O(n \log n)$

Key Properties of Big Oh Notation

Transitivity: If $ f(n) = O(g(n)) $ and $ g(n) = O(h(n)) $, then $f(n) = O(h(n))$ .
Additivity: If $ f(n) = O(h(n)) $ and $ g(n) = O(h(n)) $, then $(f + g)(n) = O(h(n))$ .
Multiplicativity: If $f(n) = O(g(n))$ , then $f(n) \cdot c = O(g(n))$ for any constant $c$ .

Common Big O Notations

Below is a table summarizing common Big O notations and their characteristics:

Complexity Class	Notation	Example Algorithms	Characteristics
Constant Time	$O(1)$	Indexing an array	Time does not vary with input size
Logarithmic Time	$O(\log n)$	Binary Search	Decreases significantly with larger inputs
Linear Time	$O(n)$	Simple loop over list	Grows directly in proportion to the input size
Linearithmic	$O(n \log n)$	Merge Sort	Combines linear and logarithmic growth factors
Quadratic Time	$O(n^2)$	Bubble Sort	Growth rapidly increases with input size
Cubic Time	$O(n^3)$	Matrix Multiplication (naive)	Growth becomes unsustainable at larger scales
Exponential Time	`$ O(2^n)` $	Recursive Fibonacci Calculation	Grows unmanageably with even small increases in $ `n $`
Factorial Time	`$ O(n!)` $	Traveling Salesman Problem	Grows extremely fast, often intractable for large $ `n $`

Conclusion

Big Oh Notation provides a high-level understanding of the algorithm's complexity. However, it focuses on the upper bound, ignoring constant factors and lower-order terms. In practice, it's crucial to consider these factors for a complete performance analysis. By helping to abstract the behavior of algorithms, Big Oh Notation remains a powerful tool for computer scientists and engineers in algorithm design and analysis.