CSci 271 Lecture Notes

Week Four, Monday: The Growth of Functions

Review of Functions

Definition 1 (page 59): A function f from set A to set B is an assignment of exactly one element of B to each element of A (my emphasis).

Definition 5 (page 61): A function f is said to be one-to-one (injective) iff f(x) = f(y) implies that x = y for all x and y in the domain of f.

Definition 7 (page 62): A function f from set A to set B is called onto (surjective) iff for every element b in B there is an element a in A with f(a) = b.

A function is a bijection (one-to-one correspondence) if it is both an injection and a surjection

Big-O Notation

Definition 1.

Example 1.

Example 2.

Example 3.

Theorem 1.

Example 4

Example 5

Example 6

The Growth of Combinations of Functions

Theorem 2

Corollary 1

Theorem 3

Example 7

Example 8


This page established September 25, 1998; last updated September 25, 1998.