Skip to main content

Consortium for Mathematics and its Applications

Product ID: 99692
Supplementary Print
Undergraduate

Evaluating the Complexity of Structures Computer Programs (UMAP)

Author: David Finkel and Gary Haggard


This module presents a mathematical study of the problem of evaluating the complexity of structured computer programs. This material is used to determine a function to describe the complexity of a structured program. Such functions can be used to determine when one algorithm to solve a problem is better than another.

Table of Contents:

INTRODUCTION

OVERVIEW

DEFINITION OF ASYMPTOTICALLY DOMINATES

PROPERTIES OF THE RELATION ASYMPTOTICALLY DOMINATES

POLYNOMIAL FUNCTIONS

APPLICATION TO MORE GENERAL FUNCTIONS

BIG-O NOTATION

THE COMPLEXITY OF AN ALGORITHM

THE COMPLEXITY OF STRUCTURED PROGRAMS
Sequence
Selection
Repetition

ALGORITHMS FOR DETERMINING IF N IS PRIME
Algorithm 1
Algorithm 2
Algorithm 3
Algorithm 4

COMPARING ALGORITHMS

SUMMARY

SAMPLE EXAM

SOLUTIONS TO EXERCISES

ANSWERS TO SAMPLE EXAM

REFERENCES

ABOUT THE AUTHORS

©1989 by COMAP, Inc.
UMAP Module
35 pages

Mathematics Topics:

Discrete & Finite Mathematics

Application Areas:

Computers & Technology , Complexity Theory

Prerequisites:

Derivatives; properties of polynomial, exponential, and log functions; equivalence relations; mathematical induction; a first programming course in a structured programming language

You must have a Full Membership to download this resource.

If you're already a member, login here.

Not yet a member?