Big-O-Notation (EN)

Big-O-Notation

The Big-O notation is a mathematical method for describing the asymptotic behavior of functions, particularly for analyzing the time and space complexity of algorithms. It provides an upper bound for the growth of resource requirements as a function of input size. It helps compare algorithms and evaluate their efficiency for large datasets. The notation is a central tool in computer science for assessing algorithm performance.

Complexity Classes

graph TD     O(1) --> O(log n) --> O(n) --> O(n log n) --> O(n²) --> O(2ⁿ) --> O(n!)          classDef optimal fill:#9f9,stroke:#333,stroke-width:2px;     classDef suboptimal fill:#ff9,stroke:#333,stroke-width:2px;     classDef inefficient fill:#f99,stroke:#333,stroke-width:2px;          class O(1),O(log n) optimal;     class O(n),O(n log n) suboptimal;     class O(n²),O(2ⁿ),O(n!) inefficient; 

Examples

• O(1) - Constant time (accessing an array element)
• O(log n) - Logarithmic (binary search)
• O(n) - Linear (linear search)
• O(n²) - Quadratic (simple sorting algorithms like Bubble Sort)
• O(2ⁿ) - Exponential (recursive Fibonacci without memoization)