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

Functions in big-O Notation

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(n²) where f(n) = An² + Bnlog(n) + n, for some constants A, B, and C all > 0.

Prove f(n) is NOT O(log(nⁿ)) where f(n) = An² 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(n²) 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(n²) 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(n²), 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).