Module 3: Algorithm Analysis

Intstance

Specific data that satisfies the input specification of a problem

Order Notation

Notation used to categorize functions into groups specified by simple functions; also called asymptotic notation

Pseudocode

CS 231’s way to describe code using a compromise between English and a model of computation

Algorithm Sketch

a description of an algorithm in sentences or point form

Paradigm

A systematic approach to designing algorithms

What is the cost of assigning a value to a variable?

θ(1)

What is the cost of using a variable?

θ(1)

What is the cost of using an arithmetic or Boolean operation or a comparison?

θ(1)

What is the cost of moving to another line in the program?

θ(1)

What is the cost of returning a value using return?

θ(1)

Cost of Iteration Management

Cost of ensuring that the loop is executed the correct number of times

Cost of Loop Body

The cost of the indented lines executed during each iteration

What is the basic costs of iteration management?

constant time per iteration

What is an example of any non-constant costs that will be add to the cost of each iteration?

calling a non-constant function to determine the size of a range or within a condition for a while loop

Loop Common Situation 1

The cost of each iteration is asymptotically the same for each iteration (that is, each iteration has a cost in for some function g(n)).

The cost of the loop = the number of iterations × cost of one iteration.

Loop Common Situation 2

The cost of iteration i is in θ(i).

The cost of the loop is θ(k²), where k is the number of iterations.

Upper Bound O

Describes an algorithm can run at most in O(?) time.

Recipe for Analyzing Worst-Case Running Time

• Break each block into blocks.

• Determine a bound on each block individually.

• Retain all dominant costs.

• Use θ if all costs are expressed in θ and can occur simultaneously and use otherwise.