Now that you’ve started learning how to use asymptotic notation to measure the runtime of a function, let’s practice with Python!
When analyzing the runtime of a function, it’s necessary to check the number of iterations the loop will perform based on the size of the input.
count function on the left takes in a positive integer of size
N and returns the number of times it takes to divide
We can analyze the runtime of this function by counting the number of iterations the
while loop will perform based on the size of the input.
Change the values of
num_iterations_64 to the number of iterations the
while loop will perform when
N is respectively
Do you notice a pattern forming? With
N being divided by
2 each iteration, we can use that to establish a big O runtime.
Change the value of
runtime to whichever one of these values you think the big O runtime is:
"N log N"