Mathematical Foundations of Algorithm Analysis

Mathematical Foundations of Algorithm Analysis

a WimpyPoint presentation owned by Mark Dettinger

Mathematical Foundations of Algorithm Analysis


Asymptotic Running Time of an Algorithm

When we analyze the running time of an algorithm, it's usually not worth to compute the exact running time. For large input sizes only the order of growth of the running time - the asymptotic running time - is relevant.
Most times it does not matter if an algorithm is 2, 3 or 10 times faster than an other algorithm. Constant factors are dwarfed by the effect of the input size.

The real question to ask when we analzye an algorithm's efficieny is: If we double the input size, how does this affect the running time of the program? Does it run twice as long? Or four times as long? Or even longer?


Asymptotic Running Times - Example

Which one is the more tedious job? (You will be told the value of n after accepting the assignment.) Adding two n-digit numbers takes time proportional to n.
Multiplying two n-digit numbers takes time proportional to n2.

Asymptotic Notations

When we talk about the running time of an algorithm, we use three different notations to give upper, lower or tight bounds of the asymptotic running time.


For asymptotic upper bounds.


For asymptotic lower bounds.


For asymptotically tight bounds.


Quiz question: Why doesn't it make sense to say: "The running time of this algorithm is at least O(n2)"


Rank the following functions by order of growth.


When an algorithm contains a recursive call, its running time can often be described by a recurrence.


How do you solve such a recurrence equation?

Solving Recurrences

Four common ways to solve a recurrence are:

Guess the solution and then prove it.

T(n) = 2 T(n/2) + n The last step holds for c>=1.

Expanding a Recurrence

Doesn't require you to guess the solution, but it may require more algebra than guessing and then proving it by induction.

Visualize the Recursion Tree

T(n) = 2 T(n/2) + n2

The Master Theorem

To solve the recurrence T(n) = a T(n/b) + f(n), compare f(n) with nlogba. This is a rather sloppy definition, but it is good enough for most functions that we will encounter. There are some more technical formalities that should be understood, however. They are explained in "Cormen, Leiserson, Rivest: Introduction to Algorithms", pages 62-63.

Multiplication revisited


Elements of Discrete Mathematics

We review the notations, definitions and elementary properties of the elements of discrete mathematics that are most relevant for the Algorithms course.

Sets, Relations, Functions




Example Graph Problem: The Party Problem

Is it possible that at a party with at least 6 people the following two conditions can both guaranteed?

Graphs - Paths and Cycles


Graph Problems




Last modified 2001-01-29

Mark Dettinger (