Big-O Notation

We are now ready to develop a formalism for classifying algorithms according to their time and space efficiencies. This formalism is known as big-O notation.

What is big-O notation?

Big-O notation can be used to describe an algorithm's time and space efficiency. It describes an upper bound on the amount of resources that will be required for the algorithm as a function of the input size (n) to the algorithm.

Time efficiency is sometimes known as time complexity or running time. Space efficiency is sometimes known as space complexity.

Watch the video below to learn about big-O notation and to hear an example where knowing the efficiency of an algorithm may have helped a software developer devise a better solution:

Recall

The logarithm function, y = log_b(n) ("the log of n to the base b"), represents the exponent y to which b must be raised to produce n. In other words, to satisfy b^y = n. Here are some examples:

Log expression	Equivalent value
log₁₀(1000)	3 (since 10³ = 1000)
log₂(32)	5 (since 2⁵ = 32)
log₂(1024)	10 (since 2¹⁰ = 1024)

In computer science we typically deal with situations where b = 2, since as we will see, we often use algorithms that split the size of the input in half (i.e., into two segments) at each step. However, for big-O notation the base is not important, so it is typically omitted and we just say log(n).

To summarize, here are some of the most common efficiency classes, sorted by slowest to fastest:

O(n!) ("factorial time")
O(cⁿ) where c is some constant ("exponential time")
O(n^c) where c is some constant >2 ("polynomial time")
O(n²) ("quadratic time")
O(nlogn) ("linearithmic time" or "log-linear time")
O(n) ("linear time")
O(logn) ("logarithmic time")
O(1) ("constant time")

For example, we would say that as the input size n grows, an O(n) algorithm is faster than an O(n²) algorithm.

What is big-O measuring?

We mentioned above that a big-O expression defines an upper bound on the amount of resources used by an algorithm. But how do we measure the amount of resources?

For time efficiency, recall from last week we are concerned with the computational time of the algorithm. The computational time is determined by the number of operations that the algorithm performs. When a computer program is executed, the code of the program is broken down into a series of simple operations, for example:

Adding two numbers together
Comparing two numbers
Fetching a value from main memory
Assigning a value to a variable
And many others!

Taken together, these fundamental operations compose an entire computer program. For some programs, we are actually able to derive an exact formula for the number of operations it performs. For example, we might be able to say that an algorithm performs 3n - 3 move operations, where n is the size of the input. To derive the big-O running time from this exact formula, we can use a couple of rules.

The rules of big-O notation

Rule 1: lower-order terms are ignored

Keep in mind that big-O defines what happens as n increases -- in theory, to infinity. Therefore, when analyzing the efficiency of algorithms, we think of n as a very large number.

When n is large, mathematical expressions involving n are dominated by their largest term (i.e., the term with the highest degree or exponent):

n	n^2/2	n/2	n^2/2 - n/2
10	50	5	45
100	5,000	50	4,950
10,000	50,000,000	5,000	49,995,000

Therefore, in big-O notation we ignore all lower-order terms and focus only on the highest order term: n² + nlogn - n becomes simply O(n²).

Rule 2: coefficients are ignored

For the same reason, we typically ignore coefficients, even on the largest term. As n grows very large, coefficients are not significant. Even a coefficient such as 1/1,000,000,000,000 is insignificant when n grows toward infinity!

For example, n²/2 + n = O(n²) because we can ignore the lower-order term (n) and can also ignore the coefficient (1/2).

Big-O and Worst-Case Analysis

An algorithm can behave differently depending on the contents of its input. For example, consider this algorithm:

def print_odd_len_list(lst):
    # if the list has an even number of elements
    if len(lst) % 2 == 0:
        return

    for item in lst:
        print(item)

Clearly, the if statement here impacts how long this algorithm takes to run. If the given lst has an odd number of elements, the function prints all of the elements, one-by-one. However, if lst has an even number of elements, the function simply returns without doing any printing. How do we analyze the effect that conditional execution (i.e., if statements) has on the running time of an algorithm?

We can break our analysis down into different cases. For print_odd_len_list(), the best case occurs when the list is an even length, because there is the least amount of work to do. For even-length lists, the function is O(1) -- no matter how long the list is, it can always immediately return!

In the worst case, an odd-length list is given. In this case, the function iterates over the entire list, and is therefore O(n).

When we're analyzing algorithms, we are typically interested in the worst case behavior when devising our big-O expression. This allows us to ignore conditional execution and just focus on the overall structure of the algorithm. This worst-case analysis is for theoretical purposes only. In real-world applications, we do consider how frequently the best case would occur, along with whether there would be an average case (i.e., somewhere between best and worst).

Still, when someone asks for the big-O analysis of an algorithm, unless otherwise specified they are asking for the performance of the algorithm in the worst case.

Big-O and Space

We can also use big-O notation to express the amount of extra space that an algorithm uses. By "extra" space, we mean memory resources that are needed to complete the algorithm, excluding the input.

In some algorithms, the only extra memory resources that are needed are some local variables, such as loop indexes or a constant number of other variables on the stack. These algorithms have a space complexity of O(1).

Other algorithms require a more significant amount of extra space. For example, an algorithm that makes a copy of a list has a space complexity of O(n), since the amount of extra space needed by the algorithm linearly increases as the size n of the input list increases.

Summary

We've covered a lot of ground in this lesson. Watch the video below to see a quick summary of big-O notation, and make sure that your understanding aligns with what it describes before moving on to the next lesson.

Data Structures and Algorithms