Problem set week 1

Exercise numbers refer to the course book.

• 1.11ab. Note that the questions are not formulated correctly. Fix the formulations, and solve the fixed questions.

• 2.2, 2.10, 2.15.

• What is wrong with the following argument?

  Let T : ℕ → ℕ. The following equations have the solution T(n) = θ(n):

  • T(0) = 0
  • T(n) = n + T(n - 1), if n > 0.

  Proof by induction over n:

  • Base case: T(0) = 0 = θ(1).

  • Step case (n > 0):

    T(n)
      =
    n + T(n - 1)
      = { Inductive hypothesis. }
    n + θ(n - 1)
      =
    θ(n).