Basic asymptotics.

∀ a>1

`an ∈ O(nᵃ)`

. It's enough to show that for n>n₀,`an ≤ anᵃ`

i.e.

`n ≤ nᵃ`

take logs (base

`n`

) 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ᶜ`

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

Some notation:

`lg n ≡ log₂ n`

;`lg² n ≡ (lg n)²`

IH:`T(n) ≤ c (lg² n)`

, for some`c≥ 1`

.`T(n) ≤ c lg² (n/2) (apply IH) = c (lg n -1)² = c [lg² n - 2lg n +1] = c lg² n - [2c·lg(n) - c]`

To force residual non-negative, we need

`2 lg(n) ≥ 1`

This holds for any integer

`n≥ 2`

String Append

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 ≤

Unlucky Pete.

Formulating problem

`N ≡ ∑ { Xᵢ |i≥ 1} Xᵢ = 1 if UP takes the course ≥ i times, 0 otherwise`

Calculating expectation

`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`

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²)`

Solving recurrences

`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})`

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

Geometric series.