15.5 Running Time Examples

Let’s look at common examples of running times starting from the least.

1) O(1)

Some Examples of O(1):


""" O(1) """
# Any assignments
x = 1  # O(1)
x += 1  # O(1)

# If statement structure
# Condition and code inside not always O(1)
if 1 == 1:  # O(1)
    print(1)  # O(1)
else:  # O(1)
    print(2)  # O(1)

# Some list operations
x = [1, 2, 4, 213]
x.append(14)  # O(1)
x[0] = 11  # O(1)

# Many, many more

O(1) is also known as constant running time, as the running time is unaffected by the input size. To clarify, even if a list is size one million, appending something at the end is still going to take the same time as it would appending something to the end of a list size five.

2) O(n)

Example:


""" O(n) """
# "Most" for loops are O(n)
for number in [123, 4, 21, 312, 41]:  # O(n)
    print(number)  # O(1)

O(n) is also known as linear running time, as the number of operations to run the code when the input is size n is a constant times n. To clarify, if a list is size one million and we are looping through and printing all of them, it would take two million operations.

3) O(n^2), O(n^3), and so on

Example:


""" O(n^2), O(n^3), etc. """
# "Most" of the time, every extra for loop
# increases running time by a factor of n

example_list = [12, 3, 214, 5, 12]
for num1 in example_list:  # O(n)
    for num2 in example_list:  # O(n)
        print(num1, num2)  # O(1)

MOST of the time, every extra nested for loop increases the running time by a factor of n. So 2 for loops is O(n^2), 3 for loops is O(n^3), and so on. Suppose a list is size one million. For O(n^2), the number of operations is a constant times one million squared. For O(n^3), the number of operations is a constant times one million cubed.

4) Many others

There are many running times not covered like logarithmic, exponential, multiple variables (not just n). The ones covered so far are most of the easier running times.

View code on GitHub.

Previous Section

4️⃣

15.4 Rules for this Course

Next Section

6️⃣

15.6 Procedure for Calculating Running Time

⚖️

Copyright © 2021 Code 4 Tomorrow. All rights reserved. The code in this course is licensed under the MIT License. If you would like to use content from any of our courses, you must obtain our explicit written permission and provide credit. Please contact classes@code4tomorrow.org for inquiries.