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.