CSC 378: Data Structures and Algorithm Analysis

How to analyze with O()

Rules for using O( )

  1. For a single statement index1.gif , whose execution time does not depend on n:

    index2.gif

  2. For a sequence of statements: index3.gif :

    index4.gif

  3. for i = 1 to index5.gif
    index6.gif

    index7.gif

  4. while (condition)
    index8.gif

    No fixed rule: must analyze to find a bound on the number of iterations.

  5. If index9.gif then index10.gif else index11.gif

    index12.gif

Pseudo-Math with O( )

  1. index13.gif

    e.g. index14.gif

  2. if index15.gif then index16.gif

    e.g. index17.gif

  3. index18.gif

Recall that index19.gif is a set of functions. Rules VI, VII, and VIII are provable if we consider index20.gif and index21.gif to act on all pairs from the two sets. For example: index22.gif .

  1. Sometimes we mix index23.gif and ordinary functions:

    e.g. index24.gif

    In this situation, index25.gif can be replaced by index26.gif .

    e.g. index27.gif

    index28.gif

    Note that the symbol index29.gif is the convention here, since the left-hand-side of the last equation is not mathematically meaningful.

  2. If index30.gif then index31.gif (used in conditionals).

An Example

index32.gif index33.gif index34.gif
index35.gif index36.gif index37.gif
index38.gif index39.gif
index40.gif index41.gif
index42.gif index43.gif
index44.gif index45.gif index46.gif
index47.gif
index48.gif




Back to the lecture index

Copyright 1998     James Stewart