---
tags: CS18Prep, 2020
title: CS18 Bridge--Running Times
---

# CS18 Bridge Assignment: Running Times

In class, we've been taking an intuitive approach to worst-case running times, summarizing our thoughts in terms of "linear", "quadratic", or "constant". But there is a more formal approach to determining the worst-case running time of a function, based on writing out a function that summarizes how many computational steps get taken on each element.

Understanding the basics of this is the main non-programming topic from CS17 that we continue to build on in CS18.

Luckily for us, CS19 covers this material with a good textbook chapter (written relative to Pyret). The material on recurrences is the part you'll particularly need for CS18 (the whole chapter builds up to that, so don't skip sections). Kathi gave a lecture on this in Fall 2018 based on the textbook chapter.

- [The textbook chapter](https://papl.cs.brown.edu/2018/predicting-growth.html#%28part._math-anon-functions%29)

- [Lecture Capture from CS-111, Dec 2018](https://brown.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=5376e59e-d1bc-45b6-bf02-a9b300f9b1b3)

- [Code handout that went with lecture capture](https://docs.google.com/document/d/1t7CQdqtZfJANw8FKpIXsBXPa9y66zq_Y2cRTztNBlao/edit?usp=sharing)

<!--
- [Lecture from CS0190, Sept 14 2018](https://brown.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=1fc33c24-b6c4-4f59-ad0a-a95b0105d612)
-->

## Exercises

For your CS18 prep, we want you to:
- write formal recurrences, and
- summarize them with big-O notation (explained in chapter and in the lecture capture) For example, O(k) (or whatever is appropriate).

for four programs:

* insertion sort
* mergesort
* quicksort
* binary search tree lookup (`has-elt` on the binary search tree assignment)

## Reflection

Write a few sentences about what you’ve learned from these problems (either on paper, in a file, etc). Also mention any questions you have (if any) based on these exercises.

## Handin

You can write these on paper (then scan them in) or use a word processor, as you prefer. Many word processors are rather poor at mathematical formulas, so you may find paper easier (fyi, most computer scientists use a tool called LaTeX for such formatting, but you are by no means expected to learn or know that for CS18).

You can submit these answers either as part of the sorting and binary search tree assignments (analyzing each function in its corresponding assignment), or all together as part of this assignment. If you do the analyses as part of the lists and binary tree assignments, you won't submit anything additional for this assignment.

Use the name `runningtimes.pdf` (or `.arr` or `.txt`) for your file.