CS 136 Tutorials - Spring 2007

Tutorial 5: big-O Notation and Proofs by Induction (June 1)

This tutorial will start by proving a function is or is not big-O of some expression. We will then move into proving big-O expressions for recursive functions. The material covered expands on main points taken from lecture module 5 (see Handouts).

  1. Functions in big-O Notation
  2. This part of the tutorial uses the definition of big-O to show that a function is big-O of an expression.

    • f(n) is big-O of ___
    • Prove f(n) is O(n2) where f(n) = An2 + Bnlog(n) + n, for some constants A, B, and C all > 0.

      Prove f(n) is NOT O(log(nn)) where f(n) = An2 for some A > 0.

      Prove f(n) is O(n), O(log(n)), O(log(n)/n), and O(1) where f(n) = Alog(n)/n for some A > 0.

    • Error ?
    • Explain the error in the reasoning below.

      O(n2) is O(n(n-1)) is O(n(n-2)) is ... O(n(n-p)) is ... O(n(2)) is O(n(1)), therefore O(n2) is O(n).

    • Prove the Following using Induction
    • Prove f(n) is O(n), where f(n) = a (if n = 0) and f(n) = b + f(n-1) (if n > 0).

      Prove T(n) is O(n2), where T(n) is O(1) for T(0) and T(1), and T(n) = T(n-2) + f(n) where f(n) is O(n).

      Find a big-O expression for P(n) and prove it, where P(n) &le a (if n is zero), P(n) &le P(n/2) + b + n (if n is even), and P(n) &le P((n-1)/2) + c + n (if n is odd).


Last modified on Friday, 19 August 2011, at 18:05 hours.