Edit the [RMarkdown source file](01time.Rmd) for this assignment in RStudio. Enter your responses after each question. When you finish, Knit the file to HTML and upload the `.html` output to Canvas.

## Running time of songs

Our textbook is [Algorithms](http://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE.pdf) by Jeff Erickson, which we will henceforth refer to as [E]. Read about the running time of songs on pages 15-16 of [E], and then answer the following questions.

> 1. Describe a song that requires $\Theta(n^3)$ time to sing the first $n$ verses. (This is problem 1(a) of [E].)

This is where your answer goes. Erase these sentences and replace them with your answer. Notice that you have to skip a line after the question so that the answer gets formatted differently from the question. If you want to make a pseudocode block, you can put it between two sets of three backticks, as follows.

```
pseudocode goes in blocks like this
    They are rendered like <pre></pre> blocks in html.
    You can indent, use special characters, etc.
```

You can include mathematical expressions using LaTeX. Just delimit them with dollar signs: $f(n) \in \Theta(g(n))$.

> 2. Do problem 2 on pp. 17-18 of [E]. Justify your answers.

## Describing algorithms

Describing algorithms in pseudocode is different from writing the code for an algorithm in a programming language. Read Section 0.4 of [E]. In particular, notice that it is OK to include things "that you've already learned how to do (like sorting, binary search, tree traversal, or singing '$n$ Bottles of Beer on the Wall')" as commands in your pseudocode. You don't need to write the pseudocode for these subroutines; just invoke them.

> 3. Describe an algorithm that inputs an array of $n$ integers and another integer $x$, and determines whether or not there are elements $a$ and $b$ in the array such that $a+b=x$. Give the running time of your algorithm. (You should be able to find an algorithm with running time $\Theta(n \log_2 n)$.)
