This article explains the importance of Big-Oh notation in computer science for evaluating and comparing the time and space complexity of algorithms.
In computer science, Big-Oh notation is used to describe the time complexity or space complexity of algorithms (Geeks for Geeks, 2024). Mathematically, it defines the upper bound of an algorithm’s growth rate, known as the asymptotic upper bound, and is denoted as f(n) is O(g(n)) or f(n) ∈ O(g(n)), pronounced f(n) is Big-Oh of g(n). The term “asymptotic” refers to the behavior of the function as its input size n approaches infinity. In the context of computer science, it describes the worst-case scenario for time complexity or space complexity. For example, an algorithm with time complexity will grow much faster than one with O(n²) as the input size increases, with n representing the number of primitive operations. Primitive operations are low-level instructions with a constant execution time, such as assigning a value to a variable, performing an arithmetic operation, comparing two values, or accessing an element in an array by its index.
Definition of Big-Oh:
Let f(n) and g(n) be functions mapping positive integers to positive real numbers.We say that f(n) ∈ O(g(n)) if there is a real constant c > 0 and an integer constant n₀ ≥ 1 such that:
f(n) ≤ c⋅g(n) , for n ≥ n₀
(Carrano & Henry, 2018)
The Graphical representation of the relationship:
Figure 1:
Big-Oh Time Complexity
The table below illustrates various O(g(n)) related to common computer science algorithms:
Table 1
Big-Oh Notation Summary
Educative (n.d.). Advantages and disadvantages of the Big-O notation. Educative.
Originally published at Alex.omegapy - Medium on August 28, 2024.
SOCIAL SHARE CARD GENERATOR