Big O Notation: Time Complexity & Examples Explained

What Is Big O Notation?

Big O notation is a mathematical notation used in computer science to describe the upper bound or worst-case scenario of an algorithm's runtime complexity in terms of the input size. It provides a standardized and concise way to express how an algorithm's performance scales as the input size grows.

Big O Notation: Formal Definition

Big O Notation is a way to describe how the time or space needed by an algorithm grows as the size of the input increases. When it is said that a function f(n) is O(g(n)), it means that f(n) will not grow faster than a certain multiple of another function g(n) once the input size is large enough. In other words, f(n) is bounded by g(n) scaled up by some constant value for large inputs.

To simplify, if a constant and a starting point can be found where this relationship holds, it means f(n) behaves in a predictable way compared to g(n) as the input size gets bigger. This helps in understanding and comparing the efficiency of different algorithms, ensuring they perform within acceptable limits for large amounts of data.

Importance of Big O Notation

1. Comparing Algorithm Efficiency: This allows us to compare the efficiency of different algorithms for solving the same problem. By looking at the Big O notation of two algorithms, we can quickly determine which one will perform better for large input sizes.

2. Predicting Algorithm Behavior: Big O notation helps us predict how an algorithm will perform as the input data grows. This is crucial for understanding algorithms' scalability and ensuring they can efficiently handle larger datasets.

3. Optimizing Code: Understanding the Big O complexity of an algorithm is essential for optimizing code. By identifying complex algorithms, developers can focus on improving those parts of the codebase to make their software more efficient.

4. Resource Management: Big O notation is also relevant for resource management, especially in resource-constrained environments such as embedded systems or server environments. It helps developers make informed decisions about memory usage, processing power, and other resources.

5. Problem-Solving Approach: When solving complex problems, knowing the Big O complexity of different algorithms can guide the selection of appropriate data structures and algorithms. This helps devise efficient solutions to real-world problems.

Understanding Big O Notation

In Big O notation, "O" represents the order of the function, and "f(n)" represents the function describing the algorithm's time complexity in terms of the input size "n." The notation "O(f(n))" signifies that the algorithm's time complexity grows no faster than a specific function of "n." Here, "f(n)" is a mathematical function describing how the algorithm's runtime increases as the input size grows.

For example:

• O(1): Constant time complexity, where the algorithm's runtime remains constant regardless of the input size.
• O(log n): Logarithmic time complexity, where the algorithm's runtime grows logarithmically with the input size.
• O(n): Linear time complexity, where the algorithm's runtime grows linearly with the input size.
• O(n log n): Linearithmic time complexity, commonly seen in efficient sorting algorithms like mergesort and heapsort.
• O(n^2): Quadratic time complexity, where the algorithm's runtime grows quadratically with the input size.

Big O Notation Examples

Let's look at some examples to see how Big O Notation simplifies functions as input size grows:

• Example 1: Simplifying a Polynomial Function

Imagine you have a function f(x)= 6x4-2x3+5. To simplify this using Big O Notation, you look at the terms and pick the one that grows the fastest as x gets bigger. In this case, 6x4 is the term that grows the quickest, while -2x3 and 5 become less important. The constant 6 in 6x4 doesn't change how we describe the growth rate, so we drop it. Thus, f(x) can be simplified to x4, and we say f(x) is O(x4).

• Example 2: Simplifying a Product of Factors

Consider the function f(x) = 3x2.(2x + 1) . First, expand this function to get 6x3+3x2. Here, the term 6x3 grows faster than 3x2 as x increases. When using Big O Notation, you ignore the constants like 6 and focus on the term with the highest growth rate. So, f(x) simplifies to x3, and we say f(x) is O(x3).

Complexity Comparison Between Typical Big Os

O(1) - Constant Time Complexity

• Description: Algorithms with constant time complexity execute in a constant amount of time regardless of the input size.
• Example: Accessing an element in an array by index.
• Comparison: Regardless of the input size, the time is the same.

O(log n) - Logarithmic Time Complexity

• Description: Algorithms with logarithmic time complexity have their runtime grow logarithmically with the input size.
• Example: Binary search in a sorted array.
• Comparison: As the input size increases, the runtime grows slowly, making it more efficient than linear time complexities.

O(n) - Linear Time Complexity

• Description: Algorithms with linear time complexity have their runtime grow linearly with the input size.
• Example: Linear search through an unsorted array.
• Comparison: The runtime increases proportionally to the input size.

O(n log n) - Linearithmic Time Complexity

• Description: Algorithms with linearithmic time complexity have their runtime grow in proportion to the input size multiplied by the logarithm of the input size.
• Example: Efficient sorting algorithms like mergesort and heapsort.
• Comparison: More efficient than quadratic time complexities but less efficient than linear or logarithmic ones.

O(n^2) - Quadratic Time Complexity

• Description: Algorithms with quadratic time complexity have their runtime grow quadratically with the input size.
• Example: Nested loops iterating over the input.
• Comparison: As the input size increases, the runtime grows quadratically, making it less efficient for large inputs.

O(2^n) - Exponential Time Complexity

• Description: Algorithms with exponential time complexity have their runtime grow exponentially with the input size.
• Example: Brute-force algorithms that try all possible combinations.
• Comparison: Extremely inefficient for large inputs, as the runtime increases rapidly with even small increases in input size.

O(n!) - Factorial Time Complexity

• Description: Algorithms with factorial time complexity have their runtime grow factorially with the input size.
• Example: Algorithms generating all permutations of a set.
• Comparison: Highly inefficient, with the runtime growing extremely fast with the input size.

Usage Of Big O Notation

Apart from the examples, here is how Big O Notation is commonly applied across various fields to simplify complex problems and aid in analysis:

• Mathematics

In mathematics, Big O Notation is often used to express how closely a finite series approximates a given function. This is especially common in cases like truncated Taylor series or asymptotic expansions, where the goal is to measure how well a simplified expression represents a more complex function as the variable grows large. By using Big O Notation, mathematicians can ignore less significant terms, focusing on the dominant behavior of the function.

• Computer Science

In computer science, Big O Notation plays a critical role in algorithm analysis. It describes an algorithm's efficiency, particularly how its running time or space requirements grow as the size of the input increases. By expressing these complexities in Big O terms, constants and lower-order terms are omitted, allowing for a clear comparison of algorithms based on their most significant factors.

Though the formal definition of Big O Notation remains consistent across fields, there are two specific applications that differ in their approach:

• Infinite Asymptotics

This usage focuses on the behavior of functions as the input grows infinitely large. It is commonly applied when analyzing algorithms or mathematical functions that deal with large-scale inputs.

• Infinitesimal Asymptotics

On the other hand, this usage examines the behavior of functions as the input approaches a very small value. This is often seen in mathematical contexts where the function's behavior near zero is of interest.

Properties of Big O Notation

Now let's look at the main properties of Big O Notation and how they describe and simplify the growth of functions:

• Reflexivity

Reflexivity means that a function is always bounded by itself. Simply put, if you have a function that describes how something grows, it will obviously grow at the same rate as itself. So, a function is always considered to be of the same growth rate as itself in Big O Notation.

• Transitivity

Transitivity helps us understand how growth rates are connected between functions. If one function grows at the same rate or slower than a second function, and the second function grows at the same rate or slower than a third, then the first function will also grow at the same rate or slower than the third. This shows how different functions relate to each other in terms of their growth.

• Constant Factor

The constant factor property tells us that multiplying a function by a constant does not change its Big O classification. So, whether a function grows quickly or slowly, adjusting its size by a fixed amount does not alter how we describe its growth rate in Big O terms.

• Sum Rule

The sum rule explains that if you add two functions that are each bounded by the same growth rate, their total growth rate will also be bounded by that rate. Essentially, the combined growth rate is determined by the term that grows the fastest among the functions being added.

• Product Rule

The product rule shows that when you multiply two functions, each with its own growth rate, the growth rate of their product is a combination of both rates. This helps in understanding how the growth rates of the individual functions affect the growth of their product.

• Composition Rule

The composition rule helps us understand how the growth rate of a function applied to another function is determined. By knowing how two functions grow individually, you can predict how their combination will behave. This provides insights into the growth of more complex functions created from simpler ones.

Big O With Multiple Variables

Big O Notation can be extended to functions with multiple variables, helping us understand how these functions grow relative to each other. When dealing with two functions, f(x,y) and g(x,y), we say that f(x,y) is O(g(x,y)) if there are constants that let us bound f(x,y)  by g(x,y) multiplied by a constant, as long as x and y are large enough. This means that as x and y get bigger, f(x,y) will not grow faster than g(x,y)scaled by some constant.

For instance, if f(x,y)f(x, y)f(x,y) is O(x2+y2), it means f(x,y) will always be smaller than x2+y2 multiplied by a constant, when x and y are large. This approach helps us grasp how functions with multiple inputs behave as those inputs grow. However, the specific domain or region where these functions are considered can influence how we apply Big O Notation, and there are different methods for generalizing this concept to functions with more than one variable.

Matters of Notation

When using Big O Notation, the statement "f(x) is O(g(x))" is commonly written as f(x) = O(g(x)). However, this use of the equals sign can be misleading, as it suggests a symmetry that isn't actually present. 

For example, while O(x) is a subset of O(x2), the reverse is not true. Such notations are sometimes called "one-way equalities" because reversing them can lead to incorrect conclusions. To avoid confusion, it’s usually clearer to use set notation, such as f(x) ∈ O(g(x)), which means that f(x) belongs to the set of functions bounded by g(x) up to a constant factor. Despite this, the equals sign is still commonly used.

List of Orders of Common Functions

Here is a list of common function types used to understand how the running time of an algorithm changes with larger inputs:

• Constant

This notation represents a constant time complexity, meaning that the time taken by the algorithm does not change with the size of the input. For instance, finding the median in a sorted array or accessing an element in a constant-size lookup table takes a fixed amount of time, regardless of input size.

• Inverse Ackermann 

This function grows very slowly and is used in specific data structures like the Disjoint-set. It describes operations that, while theoretically complex, have very efficient practical performance.

• Double Logarithmic 

Functions with this Big O time complexity grow very slowly. An example is the average number of comparisons needed in interpolation search for uniformly distributed values, which grows slower than logarithmic complexity.

• Logarithmic

Big O time complexity of logarithmic growth indicates that the time required grows proportionally to the logarithm of the input size. Binary search in a sorted array or operations in a balanced search tree are classic examples where the time complexity improves as the input size increases.

• Polylogarithmic 

These functions involve multiple logarithms. An example is matrix chain ordering on parallel machines, where complexity depends on the number of logarithmic factors.

• Fractional Power 

This represents functions where growth is between linear and quadratic. Searching in a k-d tree is an example, where complexity grows as a fractional power of nnn.

• Linear

Linear time complexity means the running time grows directly in proportion to the input size. Finding an item in an unsorted list or adding two integers with ripple carry are examples.

• n Log-Star n

This big O time complexity is used in specific algorithms like polygon triangulation. It describes a growth rate that is slightly faster than linear but slower than linearithmic.

• Linearithmic 

Functions with this complexity grow faster than linear but slower than quadratic. Examples include the fast Fourier transform and efficient sorting algorithms like heapsort and merge sort.

• Quadratic 

This represents functions where the running time grows proportionally to the square of the input size. Simple sorting algorithms like bubble sort, selection sort, and insertion sort have quadratic complexity.

• Polynomial or Algebraic 

These functions grow as a polynomial of the input size. Parsing complex grammar or finding maximum matching in bipartite graphs are examples.

• L-Notation or Sub-Exponential 

This notation describes functions that grow faster than polynomials but slower than exponential. Factoring numbers using advanced techniques falls into this category.

• Exponential 

Functions with exponential complexity grow extremely fast with increasing input size. Examples include solving the traveling salesman problem using dynamic programming.

• Factorial 

This represents functions with very rapid growth. Examples include solving the traveling salesman problem through brute-force methods or generating all permutations of a set.

Related Asymptotic Notations

Related asymptotic notations are used to compare how functions grow, each providing a different perspective on their relative growth rates:

1. Little-o Notation

Little-o notation is used to express that one function grows significantly slower than another function as the input becomes very large. When we say f(x) is o(g(x)), it implies that f(x) becomes negligible compared to g(x) for large values of x. 

More formally, for every positive constant ε, there exists a constant k such that f(x) is less than ε⋅g(x) for all x beyond a certain point. This notation is stricter than Big O notation because it requires the inequality to hold for all positive ε, not just for some fixed constant. Essentially, if a function is Little-o of another, it grows much slower in comparison and is overshadowed as x increases.

2. Big Omega Notation

Big Omega notation is used to describe functions that grow at least as quickly as a given function. This notation provides a lower bound on the growth rate of a function. There are two primary definitions:

• The Hardy-Littlewood Definition: In this definition, a function f(x) is Ω(g(x)) if f(x) is not asymptotically smaller than g(x). This means that f(x) grows at least as fast as g(x), and there exists a constant C such that f(x) ≥ C⋅g(x) for sufficiently large x. This definition is commonly used in number theory and highlights the function’s lower bound.
• The Knuth Definition: In computer science, Big Omega notation follows a similar concept but emphasizes that f(x) grows at least as quickly as g(x) beyond a certain point. Specifically, there are constants C and x0 such that f(x) ≥ C⋅g(x) for all x > x0​. This definition is useful for describing the minimum growth rate of algorithms and is often used in complexity analysis.

3. Family of Bachmann–Landau Notations

The Bachmann–Landau notations form a comprehensive system for describing various growth rates of functions. This family includes:

• Small o (Little o): This notation indicates that f(x) grows significantly slower than g(x). It is used to show that f(x) is asymptotically dominated by g(x), meaning f(x) becomes negligible compared to g(x).
• Big O: Describes functions that are bounded above by g(x), up to a constant factor. It is commonly used to express the upper limit of Big O time complexity, showing that f(x) does not grow faster than g(x) multiplied by a constant.
• Big Theta (Θ): This symbol indicates that a function f(x) grows at the same rate as g(x), both asymptotically above and below. It means f(x) is bounded both above and below by g(x) within constant factors.
• Big Omega (Ω): This notation provides a lower bound, showing that f(x) grows at least as quickly as g(x).
• Small Omega (ω): Indicates that f(x) asymptotically dominates g(x), meaning f(x) grows faster than g(x).

Time and Space Complexity

Time complexity refers to an algorithm's time to complete its execution as a function of the input size. It helps understand how an algorithm's runtime scales with different input sizes. Time complexity is typically expressed using Big O notation to describe the upper bound of the algorithm's runtime.

For example:

• O(1) represents constant time complexity, indicating that the algorithm's runtime does not change with the input size.
• O(log n) represents logarithmic time complexity, where the runtime grows logarithmically as the input size increases.
• O(n) represents linear time complexity, where the runtime grows linearly with the input size.
• O(n^2) represents quadratic time complexity, where the runtime grows quadratically with the input size.
• O(2^n) represents exponential time complexity, where the runtime grows exponentially with the input size.

Analyzing time complexity helps understand algorithm efficiency, compare different algorithms for the same problem, and predict their performance under varying input sizes.

Space complexity refers to the amount of memory an algorithm uses to execute as a function of the input size. It helps understand how much memory an algorithm requires to store data and execute operations. Similar to time complexity, space complexity is also expressed using Big O notation to describe the upper bound of the algorithm's memory usage.

For example:

• O(1) represents constant space complexity, indicating that the algorithm uses a fixed amount of memory regardless of the input size.
• O(n) represents linear space complexity, where the memory usage grows linearly with the input size.
• O(n^2) represents quadratic space complexity, where the memory usage grows quadratically with the input size.

Analyzing space complexity is essential for understanding algorithms' memory requirements, optimizing memory usage, and ensuring efficient resource utilization, especially in memory-constrained environments.

Best, Average, Worst, Expected Complexity

In this table:

• Best Case: This represents the minimum time or space the algorithm requires for any input. It's often an optimistic scenario.
• Average Case: Represents the expected time or space required by the algorithm averaged over all possible inputs. It provides a more realistic estimation of performance.
• Worst Case: Represents the maximum time or space required by the algorithm for any input. It's often a pessimistic scenario.
• Expected Case: Represents the average time or space complexity under some probabilistic model, providing insight into performance with more nuanced assumptions than simple average-case analysis.

How Does Big O Notation Make a Runtime Analysis of an Algorithm?

Here's how Big O notation facilitates runtime analysis of an algorithm:

1. Abstraction of Constants: Big O notation abstracts away constant factors and lower-order terms in the runtime expression. This allows for a high-level analysis of the algorithm's performance without getting bogged down in implementation details.
2. Focus on Dominant Terms: Big O notation emphasizes the dominant term or factor in the algorithm's runtime expression. This dominant term represents the primary factor determining the algorithm's scalability with input size.
3. Worst-Case Analysis: Big O notation describes the upper bound or worst-case scenario of an algorithm's runtime complexity. Focusing on the worst-case scenario guarantees an algorithm's maximum time to execute any input.
4. Comparative Analysis: Big O notation enables comparative analysis of algorithms by expressing their runtime complexities in a consistent format. Developers can compare algorithms for the same problem and select the most efficient one based on their Big O complexities.
5. Predictive Capability: Big O notation helps predict how an algorithm's runtime will scale with larger input sizes. This predictive capability is crucial for understanding the algorithm's scalability and performance characteristics.
6. Algorithm Design: Understanding the Big O complexity of algorithms guides the design process by highlighting areas where optimizations may be necessary. It encourages developers to choose data structures and algorithms that offer better time complexity for the problem.

Real-World Applications of Big O Notation

1. Software Development

• Algorithm Selection: When developing software, engineers often have to choose between multiple algorithms to solve a particular problem. Big O notation helps them select the most efficient algorithm by comparing their time and space complexities.
• Performance Optimization: Software developers use Big O notation to identify bottlenecks and optimize critical code sections. By understanding algorithms' time and space complexities, they can refactor code to improve performance.

2. Database Systems

• Query Optimization: Database query performance heavily relies on efficient algorithms and data structures. Big O notation helps analyze the time complexity of different query execution plans and select the most optimal ones.
• Indexing Strategies: Indexing plays a crucial role in database performance. Engineers use Big O notation to analyze the time complexity of various indexing strategies and choose the most efficient ones based on query patterns.

3. System Design

• Scalability Analysis: When designing large-scale systems, architects must ensure the system can handle increased loads efficiently. Big O notation helps analyze the scalability of different components and make design decisions accordingly.
• Resource Allocation: Understanding algorithms' time and space complexities is essential for resource allocation in distributed systems. Engineers use Big O notation to estimate different components' computational and memory requirements.

4. Machine Learning and AI

• Algorithm Selection: Different algorithms have different time and space complexities in machine learning and AI. Engineers use Big O notation to select the most suitable algorithms based on dataset size and computational resources for training and inference tasks.
• Model Evaluation: Evaluating the performance of machine learning models often involves complex computations. Big O notation helps analyze the time complexity of model evaluation algorithms and optimize them for efficiency.

5. Networking and Systems Engineering

• Routing Algorithms: Routing algorithms determine the path packets take through a network. Big O notation helps analyze routing algorithms' time complexity and select the most efficient ones for different network topologies.
• Concurrency Control: In distributed systems, concurrency control mechanisms ensure data consistency across multiple nodes. Engineers use Big O notation to analyze the time complexity of concurrency control algorithms and optimize them for high throughput and low latency.

Conclusion

Studying Big O notation is a foundational aspect of computer science and software engineering education, providing valuable skills and knowledge applicable across various career paths within the tech industry. Here are some career options and roles that individuals with expertise in Big O notation may pursue:

1. Software Engineer/Developer
2. Data Scientist
3. Data Analyst
4. Machine Learning Engineer
5. Systems Architect
6. Database Administrator
7. Network Engineer
8. Technical Advisor
9. Academy Researcher

Take the next step now and become a successful AI engineer with our AI Engineer Master's Program. Learn the top AI tools and technologies, gain access to exclusive hackathons and Ask me anything sessions by IBM and more. Get started!

FAQs

1. What is Big O notation? Give some examples.

Big O notation is a mathematical notation used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity. In computer science, it's primarily used to analyze algorithms' time and space complexity. Examples include:

• O(1): Constant time complexity, where the algorithm's runtime is constant regardless of the input size (e.g., accessing an element in an array by index).
• O(n): Linear time complexity, where the algorithm's runtime grows linearly with the input size (e.g., linear search through an array).
• O(log n): Logarithmic time complexity, where the algorithm's runtime grows logarithmically with the input size (e.g., binary search in a sorted array).

2. Why is Big O notation used?

Big O notation is used to analyze and compare algorithms' efficiency. It provides a standardized and concise way to describe how an algorithm's runtime or space requirements scale with the input size. By understanding algorithms' Big O complexity, developers can make informed decisions about algorithm selection, optimization, and system design.

3. What are time complexity and Big O notation?

Time complexity refers to the time an algorithm takes to complete its execution as a function of the input size. Big O notation expresses the upper bound or worst-case scenario of an algorithm's time complexity. It provides a high-level understanding of how an algorithm's runtime scales with increasing input size.

4. What is the other name for Big O notation?

Another name for Big O notation is asymptotic notation. It describes a function's behavior as the input size approaches infinity without considering constant factors or lower-order terms.

5. What are the rules of using Big O notation? 

The rules for using Big O notation include:

• Focusing on the dominant term: Only the term with the largest growth rate is considered.
• Ignoring constant factors: Multiplicative constants are ignored when determining the Big O complexity.
• Ignoring lower-order terms: Only the term with the highest growth rate is retained, and lower-order terms are dropped.
• Using worst-case analysis: Big O notation describes the worst-case scenario to provide an upper bound on the algorithm's complexity.
• Using additive notation for multiple terms: If an algorithm has multiple time complexities in different parts, the complexities are added together (e.g., O(n) + O(n^2) = O(n^2)).