7️⃣

15.7 Tricky Cases

Tricky Cases

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, the if 1==2 will 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 counter is incremented by one. Since the for loop iterates once regardless of the input, the running time is O(1).

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.

Previous Section

Next Section

⚖️

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.