CSC 378: Data Structures and Algorithm Analysis

FORMAL DEFINITIONS OF ASYMPTOTIC NOTATION

Overview of Asymptotic Notation

index1.gif are sets of functions.

Intuitively:

index2.gif
contains functions whose dominant term is at most that of index3.gif .
index4.gif
contains functions whose dominant term is strictly smaller than that of index5.gif .
index6.gif
contains functions whose dominant term is at least that of index7.gif .
index8.gif
contains functions whose dominant term is equal to that of index9.gif .

Definitions

Definitions of "Big Oh"

index10.gif is a set of functions.

index11.gif is in index12.gif if

index13.gif

This is read as "There exists a index14.gif such that, for all but a finite number of index15.gif s, index16.gif is bounded above by index17.gif .

In other words,

index18.gif

where index19.gif is the threshold above which this is true. This is shown in the figure, where index20.gif :

For example, consider

index21.gif

Since index22.gif once index23.gif gets large enough,

index24.gif

Let's be more rigorous: We must find a index25.gif and index26.gif such that

index27.gif

From the equation, guess that index28.gif . Then

index29.gif

Since index30.gif when index31.gif , index32.gif must be greater than index33.gif and (from the last line above) index34.gif must be greater than index35.gif .

Therefore, if index36.gif and index37.gif ,

index38.gif

and that proves that index39.gif .

Definition of "Little Oh"

index40.gif is in "little-oh" of index41.gif if

index42.gif

In other words, no matter how big index43.gif is, index44.gif is eventually bounded above by index45.gif .

In other words, index46.gif eventually is strictly smaller than index47.gif , regardless of the coefficient in front of the dominant term of index48.gif .

The Usefulness of "Little Oh"

Given Algorithm A with time index49.gif , and Algorithm B with time index50.gif :

If index51.gif then A is eventually faster than B.

For example, one sorting algorithm, A, with index52.gif will eventually be faster than another sorting algorithm, B, with index53.gif , since index54.gif .

Definition of "Omega"

index55.gif is in index56.gif if

index57.gif

In other words, index58.gif is eventually greater than index59.gif .

index60.gif is a lower bound of index61.gif .

Note that index62.gif if and only if index63.gif .

Definition of "Theta"

index64.gif is in index65.gif if

index66.gif

In other words, index67.gif and index68.gif are eventually within a constant factor of each other.

Tight Bounds

index69.gif but this isn't a "tight bound".

index70.gif is a tight bound for index71.gif if and only if

index72.gif

In other words, if there's no function, index73.gif , that lies in the gap between index74.gif and index75.gif , then index76.gif is a tight bound for index77.gif .

For example, index78.gif is not a tight bound for index79.gif because the function index80.gif lies in the gap between index81.gif and index82.gif . That is,

index83.gif but index84.gif

Summary

A word on notation: In some texts, like CLR, you may see the notation

index89.gif

This is equivalent to our notation,

index90.gif

Always use our notation.




Back to the lecture index

Copyright 1998     James Stewart