UNB/ CS/ David Bremner/ teaching/ cs3383/ tests/ solutions1

1

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.

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

  1. Concatentation is Θ(1)

    T(l) = T(l-1) + Θ(1)
         = ∑{ Θ(1)  | 0 ≤ i ≤ l} = Θ(l)
    
  2. 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.