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
- f(
`n`) is big-O of ___ - Error ?
- Prove the Following using Induction

This part of the tutorial uses the definition of big-O to show that a function is big-O of an expression.

Prove f(`n`) is O(`n`^{2}) where f(`n`) = A`n`^{2} + B`n`log(`n`) + `n`, for some constants A, B, and C all > 0.

Prove f(`n`) is NOT O(log(`n`^{n})) where f(`n`) = A`n`^{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`(`n`-1)) is O(`n`(`n`-2)) is ... O(`n`(`n`-p)) 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(`n`-1) (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(`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.