4005-800 -- Theory of Computer Algorithms

Alan Kaminsky

•

Department of Computer Science

•

Rochester Institute of Technology

•

4486 + 2220 = 6706

Home Page

Theory of Computer Algorithms

4005-800-70

Winter Quarter 2003

Course Page

4005-800-70 Theory of Computer Algorithms
Asymptotic Behavior of Functions

Prof. Alan Kaminsky -- Winter Quarter 2003
Rochester Institute of Technology -- Department of Computer Science

Introduction
Source Code
Syntax of Formulas
Plots
Log-Log Plots

Introduction

These programs display plots of functions commonly used to express the asymptotic behavior of algorithms, such as "lg n", "n", "n lg n", "n ^ 2", and "two ^ n". The plots can also be stored in image files (PostScript or PNG) using the "File-Save" menu option. The programs are available in the Computer Science Course Library.

Source Code

Package edu.rit.thcompalg.asymptotic

Class AsymptoticFunction
Class AsymptoticLogLogPlot
Class AsymptoticPlot

Syntax of Formulas

The programs let you specify the formula for a function using the following restricted syntax:

function ::= coefficient basic_function

coefficient ::= number | empty

basic function ::= power_function | exponential_function

power_function ::= power_part logarithm_part

power_part ::= n exponent | empty

exponent ::= ^ number | empty

logarithm_part ::= lg n | empty

exponential_function ::= two ^ n

number ::= <integer> | <real number>

empty ::=

Note that there must be whitespace between each token and the next. Some examples:

"n ^ 2"
"lg n"
"3 n lg n"
"two ^ n"

Plots

Class AsymptoticPlot is a main program that plots one or more AsymptoticFunctions. The asymptotic function formulas are specified on the command line in the above syntax.

Usage: java edu.rit.thcompalg.asymptotic.AsymptoticPlot x2 y2 formula . . .
X axis goes from 0 to 10*x2
Y axis goes from 0 to 10*y2

java edu.rit.thcompalg.asymptotic.AsymptoticPlot 10 10 "n" "0.02 n ^ 2"

Log-Log Plots

Class AsymptoticLogLogPlot is a main program that plots one or more AsymptoticFunctions on a log-log plot. The asymptotic function formulas are specified on the command line in the above syntax.

Usage: java edu.rit.thcompalg.asymptotic.AsymptoticLogLogPlot x1 x2 y1 y2 formula . . .
X axis goes from 1x10^x1 to 1x10^x2
Y axis goes from 1x10^y1 to 1x10^y2

java edu.rit.thcompalg.asymptotic.AsymptoticLogLogPlot 0 10 0 10 "lg n" "n ^ 0.5" "n" "n lg n" "n ^ 2"