**1**

- ∀ a>1
`an ∈ O(nᵃ)`

It's enough to show that for n>n₀,

```
an ≤ anᵃ
```

i.e.

```
n ≤ nᵃ
```

take logs of both sides

```
1 ≤ a
```

which is true.

- ∀ a>0, b > 0,
`nᵃ+nᵇ ∈ O(nᶜ)`

where c=a+b

W.l.o.g, suppose a ≤ b

```
nᵃ + nᵇ ≤ 2nᵇ
nᵇ ≤ nᶜ (take logs of both sides)
nᵃ + nᵇ ≤ 2nᶜ
```

**2** This recurrence is straightforward master theorem. Don't forget substitution method and recursion tree.

**3**

Concatentation is Θ(1)

`T(l) = T(l-1) + Θ(1) = ∑{ Θ(1) | 0 ≤ i ≤ l} = Θ(l)`

S ∘ a is Θ(|S|)

T(l) = T(l-1) + Θ(k+l) ≤ T(l-1) + c(k+l) ≤ ∑ { c(k+i) | 0 ≤ i ≤ l } ≤ ckl + cl(l+1)/2 ∈ O(kl + l²)

Ω proof would be the same, with a difference constant and ≥ instead of ≤

**4**

**a**
N ≡ ∑ { Xᵢ |i≥ 1}

```
Xᵢ = 1 if UP takes the course ≥ i times, 0 otherwise
```

**b**
E[N] = E[∑Xᵢ] = ∑ E[Xᵢ] (L.O.E.)

```
E[Xᵢ] = (1-p)ⁱ/(1-p)
E[N] = ∑ { (1-p)ⁱ/(1-p) | i ≥ 1}
= ∑ { (1-p)ⁱ | i ≥ 0}
= 1/(1-(1-p)) Geometric series
= 1/p
```

**5** The random part of the run time is how many times the `repeat`

loop runs. Note that `A[p]`

has a `1/n`

chance of being the maximum,
and apply the same analysis as for question *4* to get

```
E[N] = ∑ { (1-1/n)ⁱ | i ≥ 0} = n
```

Since each iteration is `Θ(n)`

, that gives a total of `Θ(n²)`

**6** Another linearity of expectation exercise. `Xⱼ`

is the indicator for Prof `j`

staying in their office.
E[xⱼ]=1/n

**7**

**a** `T(n) = ∑ { iᶜ ∣ 1≤ i ≤ n }`

. Bound above by `n`

times largest
term. Bound below by `n/2`

times the `n/2`

smallest term. `Θ(n^{c+1})`

**b** `T(n) = ∑ { cⁱ ∣ 1≤ i ≤ n }`

Geometric series.