Increase

Problem to Solve

For this problem, use the Python programs max_increase.py, and max_increase2.py. These both generate a random list of integers of a specified size, and then find the largest increase between any two entries of the list. (You may optionally print the list by uncommenting a line in the code.)

The two programs accomplish this task in different ways. Your task is to experimentally understand the running time of these programs. For example, to run max_increase.py with a list of size 1000, type:

$ python max_increase.py 1000

The above will produce output that looks something like this:

Generating random list of 1000 numbers.
Now searching for the max increase.
For a random list of size 1000, the max increase was
996481, between indices 70 and 252.
It took 0.0859 seconds to find.

On Gradescope, you should answer the following questions:

Part A: Run max_increase with the values 2000, 4000, 8000, 16000, 32000, and 64000. Note the number of seconds each took on Gradescope.

Part B: Repeat this using max_increase2 with the values 200000, 400000, 800000, 1600000, 3200000, and 6400000 and note on Gradescope.

Part C: What are the orders of growth of the two algorithms? Write your answers in the form O(1), O(log N), O(N), O(N^2), O(N^3), or O(2^N). Justify your answer using your data from parts A and B. Answer on Gradescope.

Distribution Code

For this problem, you’ll need some “distribution code”—that is, code written by CS50’s staff. Provided to you are two Python programs, max_increase.py and max_increase2.py. Your task is to analyze these programs. Start by downloading these files.

Download distribution files

Open cs50.dev.

Start by clicking inside your terminal window, then execute cd by itself. You should find that its “prompt” resembles the below.

$

Click inside of that terminal window and then execute

wget https://cdn.cs50.net/2026/fall/psets/6/increase.zip

followed by Enter in order to download a ZIP called increase.zip in your codespace. Take care not to overlook the space between wget and the following URL, or any other character for that matter!

Now execute

unzip increase.zip

to create a folder called sort. You no longer need the ZIP file, so you can execute

rm increase.zip

and respond with “y” followed by Enter at the prompt to remove the ZIP file you downloaded.

How to Submit

  1. Go to CS50’s Gradescope page.
  2. Click Problem Set 6: Increase.
  3. Answer Parts A, B, and C in the text boxes provided.
  4. Be sure to save your answer on Gradescope, and press Submit & View Submission when you’re done!