Introduction to big O notation and the analysis of algorithms.

Michael Monagan, CECM, SFU

Thursday February 27th, 9:00am-10:20am in K 9509.

Abstract:

To determine the running time of an algorithm,
computer scientists count either bit operations or arithmetic operations.
Then they express the count in big O notation.
If we count bit operations we get the "bit complexity" of an algorithm
which basically tells us how long the algorithm will take.
If we count arithmetic operations we get the "algebraic complexity".

As an example of algebraic complexity, the high school algorithm
for multiplying two polynomials of degree d over a field F
does (d+1)^2 multiplications and d^2 additions.
Expressed in big O notation this is O(d^2) 
arithmetic operations in the field F.

This tutorial will formally define O(f(d)) as a set and
show how one uses it to analyze an algorithm.  We will look
at the algebraic properties of big O notation used in the
analysis of algorithms.

This tutorial is aimed at mathematics students.
No computing background is needed.