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.
The count function on the right takes in a positive integer of size N and returns the number of times it takes to divide N by 2 until N reaches 1.
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.
Instructions
Change the values of num_iterations_1, num_iterations_2, num_iterations_4, num_iterations_32, and num_iterations_64 to the number of iterations the while loop will perform when N is respectively 1, 2, 4, 32, and 64.
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:
"1""N""log N""N log N""N^2""2^N""N!"