There are many cases where the running time is different from what it seems from a glance. In this section, we are going to go over a few of the common ones.
One of them being tricky if statements. Take a look at this example.
# Tricky if statements ex_list = [1, 23, 421, 32] if 1 == 2: for num in ex_list: print(num) else: print(ex_list)
At first glance, you may think the running time is O(n) where n is the number of elements in the input list because of the for loop. However,
if 1==2will ALWAYS result in False regardless of input, meaning the for loop under it, will never happen. Because of this, the running time is just
O(1)since the if statement will go to else every time.
Another tricky case is when a loop ends prematurely. Take a look at this example.
# Loops ending prematurely ex_list = [1, 23, 421, 32] counter = 0 for num in ex_list: counter += 1 print(num) if counter == 1: break
When you first look at the code, you may think the running time is
O(n)where n is the number of elements in the input list because of the for loop. However, the for loop ALWAYS iterates once regardless of the input because there is a break statement after
counteris incremented by one. Since the for loop iterates once regardless of the input, the running time is
There are many other cases that have tricky running times, and they happen regardless of input. Almost all of them can be found if you look at the code closely and see which part of the code doesn’t run or ends early.
View code on GitHub.