Due: Wednesday, April 16, at 10:00pm

Starter file: computational_complexity.pdf
Upload solutions via Gradescope

Goals

This assignment is designed to help you with the following:

• analyzing nested loops for computational complexity
• start thinking about functions in terms of big-O

Collaboration policy

For this assignment, you may work alone or with a partner, but you must write up all of your answers yourself. (It is therefore unexpected for two submissions to be completely identical.) You may have at most one partner.

You may also discuss the assignment at a high level with other students. You can discuss the assignment with Tanya, our prefect, or any course staff.

You should list any student or course staff with whom you discussed the assignment (you don’t have to include prefect sessions), and the manner of discussion (high level, partner, etc.) in the reflection at the end of the assignment.

If you work alone, you should say so instead.

Assessment

To demonstrate proficiency, your submission needs to:

• give correct numerical and formulaic answers to the various questions
• give justifications for at least some answers
• include a reflection in your response to the last question of the assignment

To demonstrate mastery, your submission needs to:

• demonstrate proficiency
• give compelling justifications for all answers
• include your collaboration statement in your response to the last question of the assignment

Assignment overview

See the assignment handout for instructions. This is assignment does not require you to write any code.

Reflection

Were there any particular issues or challenges you dealt with in completing this assignment? How long did you spend on this assignment?

Write a brief discussion (a sentence or two is fine) in your response to the last question in the assignment.

Here are some examples:

• Reflection:

I had some trouble making sense of question 1(d), so I wrote out the expected print statements on paper first.

I had to refer to my course notes to find what n₀ and c meant.

I spent 6 hours on this assignment.

• Reflection:

I started late, so I had to rush my explanations.

I really don’t understand how n and n₀ are different.

I spent 5 hours on this assignment.

• Reflection:

This went fine; I mixed up n₀ and c but found what I needed in the assigned reading.

I spent 3.5 hours on this assignment.