York University - CSE 3101 - Summer 2006
Phuong Nguyen

Summary of Lecture 1:

1. Asymptotic notations [Reference: Section 3.1]
big O, big Omega and Theta notations
There were plenty of examples and proofs.

A note: Section 3.2 is useful if you forget some basic functions.


2. Input representation
The stress is on realizing the difference between the value
of an integer and the length of its binary representation.

An example is the trivial algorithm for Primality checking,
which runs in exponential time.


3. Proof technique: Proof by induction
An example is to show that 1 + 2 + ... + n = n(n+1)/2
Another example: time analysis and proving the correctness of
the Insertion-sort algorithm.

There is a short discussion of Induction in Section A.2
Check Section 2.1 for the Insertion-sort algorithm.