Analysis of Algorithms

This material is only intended as a brief review of the important concepts covered in CSC 172.

When solving a problem on a computer, we typically seek an algorithm that makes efficient use of the computer resources (especially time and space).

An important criterion for evaluating an algorithm is how long it takes (or how much memory it takes) to solve problems of various sizes.

The analysis of algorithms is a mathematical approach to describing the time and space needs of an algorithm in terms of the problem size.

Big-Oh notation is used to hide constant factors (details) that are not part of the big picture. If the running time of a program is O(n), that means the running time is c*n time units, where c is a constant.

T(n) (the running time of a program with input of size n) is said to be O(f(n)) if there exists integers n0 and c such that T(n) <= c*f(n) for all n >= n0. If T(n) is O(f(n)), where f(n)=n^2, then this means that for all but a few (ie., finite number of) cases (namely those cases where the input is of size less than n0), the program will require about (ie., within a constant factor of c) n^2 steps.