Evaluating the Complexity of Structures Computer Programs (UMAP)

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