Rank the following functions of $n$ by order of growth (starting with the slowest growing). Functions with the same order of growth should be ranked equal.

(a) $\log n^3$, $n$, $n^2 \log n$, $4^{\log n}$, $\log \sqrt{n}$, $n + \log n^4$, $2^{\log 16}$, $n^{-1}$, $16$, $n^{\log 4}$

(b) *(Note: This part is not much different from (a) and provided for extra practice. You may want to skip it the first time you do the exercises.)*

$1$, $n$, $n^{-2}$, $\log 3$, $n + \log n$, $\log n^2$, $16^{\log n}$, $\sqrt n \log n$, $\log n$, $n^{\log 16}$

Prove by induction:

(a) For every integer $𝑛 \ge 5$, $2^n > 𝑛^2$

(b) $\sum_{i=1}^{n} 2i-1\ = n^2$

(c) $\sum_{i=0}^{n} x^i\ = (1-x^{n+1})/(1-x)$

*Note: Additional induction exercises are provided on the slides*

We define the problem CountInInterval as follows:
*Given an array $A$ of $n$ integers, and two integers $p$ and $q$, count the number of elements of $A$
that are at least $p$ and at most $q$.*

(a) Give an algorithm for CountInInterval.*Don't forget to prove correctness and analyze the running time.*

(b) Apply your algorithm on the weather data provided on the course website.

In [ ]:

```
```