UNB/ CS/ David Bremner/ teaching/ cs3383/ tests/ solutions1
1. 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ᶜ
``````
2. This recurrence is straightforward master theorem. Don't forget substitution method and recursion tree.

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

4. 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 ≤

5. 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
``````
6. 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²)`

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