What is a plain English explanation of Big O notation?
Data Structures & Algorithms practice on Codemia
Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.
Big O notation is a fundamental concept in computer science and mathematics, used to describe the efficiency of algorithms, particularly with respect to time and space (memory) complexity. It helps developers and computer scientists understand the upper limits of an algorithm's performance, especially as input size grows to infinity. Below, we'll explore Big O notation in plain English, delve into some technical aspects, and provide examples to clarify its purpose and application.
Understanding Big O Notation
What is Big O Notation?
Big O notation is a mathematical representation used to describe how the runtime or space requirements of an algorithm grow as the input size increases. Instead of focusing on exact measurements, it provides an asymptotic analysis that describes the upper bound, or worst-case scenario, of an algorithm's performance.
Why Use Big O Notation?
- Performance Analysis: It allows us to gauge an algorithm's efficiency, comparing it with others and choosing the most appropriate one based on size constraints.
- Scalability: It helps in predicting how an algorithm will perform as data sets get larger, which is crucial for scalability.
- Clarity and Communication: It offers a common language to discuss and compare algorithms within the tech community easily.
Common Big O Notations
Here's a table that summarizes some of the most common Big O notations:
| Big O Notation | Name | Description | Example |
| Constant Time | The algorithm's performance is the same regardless of the size of the input. | Accessing an array element | |
| Logarithmic Time | The algorithm's performance increases logarithmically as the input size grows. | Binary search | |
| Linear Time | The performance grows linearly with the increase in input size. | Looping through an array | |
| Linearithmic Time | A combination of linear and logarithmic growth; this is common in efficient sorting algorithms. | Merge sort, Quick sort | |
| Quadratic Time | Performance grows quadratically as the input size increases, usually with nested loops. | Bubble sort, Selection sort | |
| Exponential Time | The algorithm's performance doubles for every addition to the input size, often in recursive problems. | Fibonacci sequence | |
| Factorial Time | Performance grows exceedingly rapidly as input size increases, common in permutations. | Traveling salesman problem |
Example: Understanding Big O Through Binary Search
Consider the binary search algorithm which operates on sorted data. It halves the search space with each step, resulting in logarithmic time complexity, . Here's how it works:
- Start with a sorted array and a target value.
- Split the array into two halves and determine which side the target value lies on.
- Narrow down to the half that contains the target.
- Repeat the above steps until the target is found or the search space is empty.
This algorithm is much more efficient for larger data sets compared to a linear search, which has a complexity of because it checks each element sequentially.
Technical Explanation
Big O notation focuses on the term in the function that grows the fastest as the input size increases. Therefore, constants and lower-order terms are typically ignored. For instance, if an algorithm has a time complexity described by the expression , we consider it as , since the constant factor (6) and the constant term (4) become negligible with large values of .
Key Considerations
- Worst-Case vs Average-Case: Big O notation generally describes the worst-case scenario. However, in practical terms, an average-case analysis can also be useful, even though it's less often discussed in the context of Big O.
- Space Complexity: While Big O is commonly associated with time complexity, it can also describe space complexity, which refers to the amount of working storage an algorithm needs.
- Amortized Time Complexity: This is relevant for algorithms where the cost of operations varies widely. For example, dynamic array resizing may involve occasional expensive operations, but the average or amortized cost per operation remains low.
- Trade-offs: Often, algorithms involve trade-offs between time and space complexity. Improving one may worsen the other, making it crucial to balance them based on specific requirements.
Understanding Big O notation is vital for optimizing and understanding the potential constraints of algorithms in software development and computer science. Whether you're a student learning about algorithms or a seasoned developer tackling efficiency problems, mastering Big O can significantly enhance your problem-solving toolkit.
Related reading
- What is a purely functional data structure that efficiently implements rendering to an image?
- What is a super-recursive algorithm?
- What is a term-vector algorithm?
- What is a tidy algorithm to find overlapping intervals?
- What is an efficient algorithm for counting the number of triangles in a graph?
- What is an efficient algorithm to find whether a singly linked list is circular/cyclic or not?
- What is a segmentation fault?
- What is a threshold in a Precision-Recall curve?

DSA Fundamentals
Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.
View the courseTrack what you have practised
A free account saves your progress, solutions and study plan across every problem on Codemia.
Data Structures & Algorithms practice on Codemia
Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.