15.6 Procedure for Calculating Running Time

Now you know the common running time examples, we have the tools to calculate the running time of most algorithms.

Let this be the code that will be used as an example


# This code will get all the odd birthdays and print it
birthdays = [12, 4, 21, 11, 24]

odd_birthdays = []
for birthday in birthdays:
    if birthday % 2 == 1:
        odd_birthdays.append(birthday)

print(odd_birthdays)

1) Calculate the running time for each line


# This code will get all the odd birthdays and print it
birthdays = [12, 4, 21, 11, 24]  # O(1)

odd_birthdays = []  # O(1)
for birthday in birthdays:  # O(n)
    if birthday % 2 == 1:  # O(1)
        odd_birthdays.append(birthday)  # O(1)

print(odd_birthdays)  # O(1)

2) For each of the for loops, everything under it gets multiplied by the running time of the for loop (Think about it, each of the operations under the for loop gets repeated for how many times the loop iterates).


# This code will get all the odd birthdays and print it
birthdays = [12, 4, 21, 11, 24]  # O(1)

odd_birthdays = []  # O(1)
for birthday in birthdays:  # O(n)
    if birthday % 2 == 1:  # O(1)*O(n) = O(n)
        odd_birthdays.append(birthday)  # O(1)*O(n) = O(n)

print(odd_birthdays)  # O(1)

3) Add all the running times up.


# This code will get all the odd birthdays and print it
birthdays = [12, 4, 21, 11, 24]  # O(1)

odd_birthdays = []  # O(1)
for birthday in birthdays:  # O(n)
    if birthday % 2 == 1:  # O(1)*O(n) = O(n)
        odd_birthdays.append(birthday)  # O(1)*O(n) = O(n)

print(odd_birthdays)  # O(1)

# Sum = O(1) + O(1) + O(n) + O(n) + O(n) + O(1)
# Sum = 3*O(1) + 3*O(n)

4) Eliminate constants and lower order terms


# This code will get all the odd birthdays and print it
birthdays = [12, 4, 21, 11, 24]  # O(1)

odd_birthdays = []  # O(1)
for birthday in birthdays:  # O(n)
    if birthday % 2 == 1:  # O(1)*O(n) = O(n)
        odd_birthdays.append(birthday)  # O(1)*O(n) = O(n)

print(odd_birthdays)  # O(1)

# Sum = O(1) + O(1) + O(n) + O(n) + O(n) + O(1)
# Sum = 3*O(1) + 3*O(n)
# Final Running Time = O(n)

Compared to O(n), O(1) is a lower-order term. The 3’s are the constants. So, we remove O(1) and the 3's. and are left with just O(n)

View code on GitHub.

Previous Section

5️⃣

15.5 Running Time Examples

Next Section

7️⃣

15.7 Tricky Cases

⚖️

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.