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.
    
    
    
    

O-notation


For asymptotic upper bounds.
    
    
    
    

Omega-notation


For asymptotic lower bounds.
    
    
    
    

Theta-notation


For asymptotically tight bounds.
    
    
    
    

Examples


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

Exercise


Rank the following functions by order of growth.
    
    
    
    

Recurrences


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

Examples

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


    
    
    
    

Graphs


    
    
    
    

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


    
    
    
    

Trees


    
    
    
    

Last modified 2001-01-29


Mark Dettinger (mdettinger@arsdigita.com)