Efficiency and Big-O Notation

With every new data structure and algorithm that we have learned, we have also discussed the efficiency implications. We will continue to do so in this course, and will also learn new ways of evaluating the efficiency of algorithms in terms of time and space.

We have been using big-O notation to describe efficiency. To remind yourself of the basics of big-O notation, watch the video below:

To summarize:

Big-O notation is a measure of an algorithms efficiency
It describes the efficiency as a function of the size of the input, n
When given an expression that represents the number of operations of an algorithm, the corresponding big-O notation can be calculated by ignoring lower-order terms and constants
Other heuristics can be used to derive big-O expressions, such as by analyzing loops
It's important to remember that big-O notation is a simplified way of describing efficiency that focuses on the worst-case behavior of an algorithm; in practice, we care about all cases

Check your understanding

Say that there exists two algorithms, A and B, to solve a problem. Algorithm A is O(n), and algorithm B is O(n²). We know that algorithm A is considered a faster algorithm in general. However, for an input of size n = 1,000,000, does algorithm A necessarily take less time than algorithm B?

Click to reveal the answer.

Answer. No. Remember that big-O notation describes an algorithm's asymptotic running time behavior, i.e., how long it will take to run as the input size grows to infinity. Big-O notation is helpful to describe general classes of efficiency, but for practical uses, constants and lower-order terms do make a difference.

For example, algorithm A may be O(n) but have high constant terms associated with it. Meanwhile, algorithm B may indeed be O(n²), but have relatively lower constant terms, making it reasonably fast for some values of n, such as n = 1,000,000.

Check your understanding

Consider the following function:

def mystery(lst):
    for i in range(len(lst)):
        if lst[i] % 2 == 1: # i is odd
            lst[i] += 1

    total = 0
    for i in range(len(lst)):
        for j in range(i):
            if lst[i] > lst[j]:
                total += 1
    return total

What is the big-O running time of the function?

Click to reveal the answer.

Answer. The first for loop has a running time of O(n), since the loop bound is some function of the size of the list (n). The second loop is O(n²), since the outer loop is O(n) and the inner loop is O(n) (since it depends on the outer loop variable i). Our expression for the big-O running time is therefore O(n) + O(n)*O(n), which is O(n²).

Course Name

Efficiency and Big-O Notation