Tutorial 5: bigO Notation and Proofs by Induction (June 1)This tutorial will start by proving a function is or is not bigO of some expression. We will then move into proving bigO expressions for recursive functions. The material covered expands on main points taken from lecture module 5 (see Handouts).
This part of the tutorial uses the definition of bigO to show that a function is bigO of an expression. Prove f(n) is O(n^{2}) where f(n) = An^{2} + Bnlog(n) + n, for some constants A, B, and C all > 0. Prove f(n) is NOT O(log(n^{n})) where f(n) = An^{2} 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. Explain the error in the reasoning below. O(n^{2}) is O(n(n1)) is O(n(n2)) is ... O(n(np)) is ... O(n(2)) is O(n(1)), therefore O(n^{2}) is O(n). Prove f(n) is O(n), where f(n) = a (if n = 0) and f(n) = b + f(n1) (if n > 0). Prove T(n) is O(n^{2}), where T(n) is O(1) for T(0) and T(1), and T(n) = T(n2) + f(n) where f(n) is O(n). Find a bigO 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((n1)/2) + c + n (if n is odd). 

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