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)
View code on GitHub.