Summary - Big-O

Practice Big-O with a mini task computing a function's growth rate.

Summary - Big-O

In this group you learned time complexity, Big-O notation and common growth rates. Big-O gives the worst-case upper bound.

O(1) is fastest, O(n^2) is slow. On large inputs, lower Big-O always wins.

Exercise Find max

Write find_max(arr). Find the largest with a for loop and return. Print 9 with print(find_max([3, 7, 2, 9, 5])).

Show example solution

def find_max(arr):
    # Find max
    max_val = arr[0]
    for x in arr:
        if x > max_val:
            max_val = x
    return max_val
print(find_max([3, 7, 2, 9, 5]))

Test yourself

Summary - Big-O: match the terms

O(1)

Constant
O(n)

Linear
O(log n)

Logarithmic
O(n^2)

Quadratic

Big-O notation

Big-O represents the ____ of the worst case.

Show answer

Big-O represents the upper bound of the worst case.

Which is an O(n) algorithm?
- Binary search
- Array access
- Bubble sort
- Linear search
Show answer

Linear search — Linear search is O(n).

Next lesson: What is an array?

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies