Computational Complexity

Solving Computational Problems

Topics

ÒComplexityÓ in the
algorithm-analysis context

Functions associated with a program

Running time T(n)

Possible size measures n
for T(n)

Primitive Operations

Is multiplication really ÒprimitiveÓ?

Size of Numerals

Does Numeral Radix Matter?

log₂ is the norm

Asymptotic Analysis

Step Counting

Straight-Line Code

Loop Code

Non-Numeric Loop Control

Recursive Code

Recurrence Formulas
represent time for recursive expressions

Solving Recurrence Formulas
One Method: Repeated Substitution

Solving Recurrence Formulas
Another Example

Try These

GaussÕ 3rd Grade Technique

Approximate Solutions

ÒOÓ Notation

Notation Abuse

Words for Functions

Why Asymptotic Complexity Matters
Running Time as a function of Complexity

Allowable Problem Size
as a Function of Available Time

ÒOÓ Notation

Rules for ÒOÓ
Additive Rule

Multiplicative Rule

Transitivity Rule

Derivative Rule

Limit Rule

Tight Bounds

Example: log(n) ë O(n^1/2).

Black-box vs. White-box Complexity

Black-Box Complexity

Doubling Input Size

Black-Box Complexity

Use Empirical Analysis to Predict

Sorting Programs:

The Òfruit fliesÓ of
algorithm analysis

Examples: Sorting Programs

Result Tabulation from turing runs
(times in ms.)

Example: minsort

White-Box Complexity

Analysis of Typical Loops

Analysis of Actual Programs

minsort:
sorting by selecting minima

minsort

insertion sort in rex

recurrence for isort

recurrence for insert

returning to
recurrence for isort

Is O(n²) the
best we can do
for sorting?

Algorithm Speedup Techniques

Technique #1:
Divide-and-Conquer

Tony Hoare

Quicksort Illustrated

Quicksort Analysis

Another Divide-and-Conquer Sort
Mergesort

Bottom-Up Mergesort

Bottom-Up Mergesort Example

Bottom-Up Mergesort Analysis

Bottom-Up Mergesort in rex (1)

Bottom-Up Mergesort in rex (2)

Top-Down Mergesort Example

Alternate ways to split

Top-Down Mergesort Analysis

Technique #2:
Using data values to do selection

Bucket Sort

Analysis of Bucket Sort

Radix Sort

Analysis of Radix Sort

Demo of Radix Sort

Technique #3:
Use a Tree instead of Linear List

Heapsort

Laurence J. Peter

The Peter Principle

A Hierarchy

The Peter Principle
applied to Sorting

A Heap

A Heap?

The Two Phases in Heapsort

Phase I: Forming a Heap

Combination as a Tournament

Analysis of forming a heap from two sub-heaps

Iterating sub-heap formation from leaves to root

Illustrating Phase I

After Level 1 Heap Formation

Level 2 Heap Formation

After Level 2 Heap Formation

Level 3 Heap Formation

After Level 3 Heap Formation

Heapsort Phase II

Retiring the maximum

Filing the hole

Filling the hole

Result of the tournament

The cost of keeping
the heap happy

The Rest of Phase II illustrated

Phase II, step 2, continued

Phase II, step 3

Phase II, step 3, continued

Phase II, step 4

Phase II, step 5

Phase II, step 6

Phase II, step 7

Phase II, step 8

Phase II, step9

Phase II, step 10

Phase II, step 11

Phase II, step 12

Phase II, step 13

Phase II, step 14

Phase II, step 15

Conclusion of Phase II

Where to put the retirees?

Phase II with Retiree Placement

Node Numbering

Array Node Numbering
Permits Read-out of Sorted Data

Use as a Tree:
Finding your parents/children

Heapsort Code (1)

Heapsort Code (2)

Heapsort Summary

Priority Queue

Priority Queue Applications

Lower-Bound for Sorting

Derivation of the
Sorting Lower-Bound

Sorting Summary