Time complexity

Learn how runtime grows with input size.

An algorithm's time complexity describes how its running time grows as the input size increases. Larger input means longer runtime.

For example, scanning an array of n elements takes n steps; doubling the input doubles the time.

Growth rate

Different algorithms have different growth rates. One may halve the input each step, another may visit every element.

The growth rate determines the difference on large inputs. A lower growth rate means a more efficient algorithm overall.

Write array_sum(arr). Sum elements and return. Print 10 with print(array_sum([1, 2, 3, 4])).

Show example solution

def array_sum(arr):
    # Sum elements
    total = 0
    for x in arr:
        total = total + x
    return total
print(array_sum([1, 2, 3, 4]))

Growth rate

A lower growth rate means a more ____ algorithm.

Show answer

A lower growth rate means a more efficient algorithm.