View presentation

Section 1: Background

Very early on in Tim’s talking career, Tim had developed a small habit of rambling during some of the talks he was giving. In the best case scenarios, he was able to get his point across in a few sentences. However, in the worst case scenarios, the audience would begin to lose sight of the points he was trying to make, leading to an inefficient speech. In the end, Tim was able to mitigate this issue and he has grown into a fan-favorite speaker all over the world. How did he do it?

By analyzing runtime. In this lab, you will be able to calculate and see the differences in runtimes of efficient vs. inefficient functions through plotted graphs, similar to how Tim was able to use his knowledge of runtime analysis to help him become a renowned speaker.

What is Runtime?

Runtime (or Execution Time) is the time it takes a computer to execute a program. Runtime is an important metric that is often used to determine the efficiency of a function. Each program has a best-case runtime and a worst-case runtime. The reason for this is because the runtime of a program is not static. For example, the size of a datafile may affect the iterations a program must perform, which makes the runtime depend on the size of the file.

Worst-case runtime is the most commonly used metric because we must always account for the worst-case scenarios (i.e. a data file with hundreds of inputs).

Section 2: Evaluating Runtime

Note: This program uses matplotlib to create and save the graphs. If you are unable to run the program, you may need to install matplotlib. Run the following command in your terminal:

$ pip3 install matplotlib

IMPORTANT: Since this program uses matplotlib in order to be able to create the graphs and save them to your directory, you will need to head over to the Terminal and run pip3 install matplotlib.

Part 1: Two Distinct Functions

distinct1 and distinct2 are two distinct functions that have the same functionality of adding elements from a list to a data structure if the new element is distinct. However, these two functions have different runtimes. In the best-case scenario, the two functions both run in constant time, but in the worst-case scenario distinct1 is slower with a quadratic runtime compared to distinct2‘s linear runtime.

Look at distinct1 and distinct2. How do these functions differ in implementation, and how would that affect the runtime of the functions given different cases? In what cases do distinct1 and distinct2 have the worst possible runtime?

Task 1: Construct an input to distinct1 and distinct2 which would give them the worst case runtime. That value should be returned by worst_case_input.

Part 2: Graphing Runtime

One great way to be able to see the differences in runtimes of efficient vs. inefficient functions is through plotted graphs.

Task 2: Define the generate_graphs function according to the stencil. This method is in charge of calling the helper methods, respectively, in order to generate the graphs which show the runtimes of distinct1 and distinct2 on the best_case_input and worst_case_input.

Part 3: Running File

Task 3: Run the file runtime_lab.py in your terminal.

After running the program, you should see four images in your directory (best1.png, best2.png, worst1.png, worst2.png). Sometimes you must go to your folder/directory in Finder in order to see the images. You can also open these images directly in VSCode. These images will show how the runtime increases as the size of the input also increases.

Section 3: You’re All Set!

Success! Once you have completed both methods and the graph images are saved in your directory, notify your TA!