Algorithm Analysis Chapter 4

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Algorithms

⚫ Algorithms are designed to solve problems.

⚫ A problem can have multiple solutions.

How do we determine which

solution is the most efficient?

Chapter 4: Algorithm Analysis –2

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Execution Time
⚫ Measure execution time:
⚫ construct a program for a given solution.
⚫ execute the program.
⚫ time it using a “wall clock”.

⚫ Dependent on:
⚫ amount of data
⚫ type of hardware and time of day
⚫ programming language and compiler

⚫ Analyse an algorithm’s efficiency independent of

the implementation details
Chapter 4: Algorithm Analysis –3
© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Complexity Analysis

⚫ What if we examine the solution itself and

measure critical operations:
⚫ logical comparisons
⚫ assignments
⚫ arithmetic operations

Chapter 4: Algorithm Analysis –4

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Example Algorithm

⚫ Given a matrix of size n x n, compute the:

⚫ sum of each row of a matrix.
⚫ overall sum of the entire matrix.

Chapter 4: Algorithm Analysis –5

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 –
© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Compare the Results

⚫ Number of additions: v1: 2n2 v 2: n 2 + n

⚫ Second version has fewer additions (n > 1)
⚫ Will execute faster than the first.
⚫ Difference will not be significant.

Both algorithms execute on the

same order of magnitude, n2

Chapter 4: Algorithm Analysis –7

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Growth Rates

⚫ As n increases, both algorithms increase at approx

the same rate:

n 2n2 n2 + n
10 200 110
100 20,000 10,100
1000 2,000,000 1,001,000
10,000 200,000,000 100,010,000
100,000 20,000,000,000 10,000,100,000

Chapter 4: Algorithm Analysis –8

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Growth Rates

Chapter 4: Algorithm Analysis –9

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Big-O Notation

⚫ No need to count precise number of steps.

⚫ Classify algorithms by order of magnitude.
⚫ execution time
⚫ space requirements

Approximates actual number of

steps or actual storage in terms
of variable-sized data sets.

Chapter 4: Algorithm Analysis –10

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Big-O Definition

⚫ Given a function T(n)

⚫ # of steps required for an input of size n.
⚫ Ex: T2(n) = n2 + n

⚫ Suppose there exist a function f(n) for all

integers n > 0 such that
T(n) < c f(n)

for some constant c and for all large values of n

Chapter 4: Algorithm Analysis –11

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Big-O Definition

⚫ Then, the algorithm has a time-complexity of or

executes “on the order of” f(n)
⚫ We use the notation: O( f(n) )
⚫ Big-O is intended for large values of n.

f(n) indicates the rate of growth

at which the run time increases
as the input size increases.

Chapter 4: Algorithm Analysis –12

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Big-O Example (v.1)

⚫ Consider the previous sample algorithms.

⚫ Version 1: T1(n) = 2n2

T1(n) < c f(n) Let c = 2

2n2 < 2n2

O( n2 )

Chapter 4: Algorithm Analysis –13

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Big-O Example (v.2)

⚫ Consider the previous sample algorithms.

⚫ Version 2: T2(n) = n2 + n

T2(n) < c f(n) Let c = 2

n2 + n < n2 + n 2
n2 + n < 2n2

O( n2 )

Chapter 4: Algorithm Analysis –14

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Upper Bound

⚫ There is more than one f(n) for an algorithm.

n2 + n < c f(n)
⚫ n2 is not the only choice
⚫ f(n) could be n2, n3, n4

Objective: find an f(n) that

provides the tightest (lowest)
upper bound.

Chapter 4: Algorithm Analysis –15

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Constant of Proportionality

⚫ Is it important?
⚫ Consider two algorithms:
⚫ O(n2), with c = 1
⚫ O(2n), with c = 2

n n2 2n
10 100 20
100 10,000 200
1000 1,000,000 2,000
10,000 100,000,000 20,000
100,000 10,000,000,000 200,000 50K more operations

Chapter 4: Algorithm Analysis –16

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Constant of Proportionality

Chapter 4: Algorithm Analysis –17

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Constructing T(n)

⚫ We don't count total number of specific

instructions (math operations, comparisons, etc)
⚫ Assume each basic statement takes the same time,
constant time.
⚫ Total number of steps required:

T(n) = f1(n) + f2(n) + ... + fk(n)

Chapter 4: Algorithm Analysis –18

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Choosing the Function

⚫ Given T(n), choose the dominant term.

T(n) = n2 + log2n + 3n

n2 dominates the other terms (for n > 3)

n2 + log2n + 3n < n2 + n2 + n2
n2 + log2n + 3n < 3n2

Chapter 4: Algorithm Analysis –19

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Choosing the Function

⚫ What is the dominant term for the following

expression?

T(n) = 2n2 + 15n + 500

When n < 16, 500 dominates.

When n > 16, n2 is the dominate term.

Chapter 4: Algorithm Analysis –20

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Classes of Algorithms

⚫ Many algorithms have a time-complexity selected

from a common set of functions.

f() Common Name

1 constant
log n logarithmic
n linear
n log n log linear
n2 quadratic
n3 cubic
an exponential

Chapter 4: Algorithm Analysis –21

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Classes of Algorithms

Chapter 4: Algorithm Analysis –22

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Evaluating Python Code

⚫ Basic operations only require constant time:

⚫ x = 5
⚫ z = x + y * 6
⚫ if x > 0 and x < 100

⚫ What about function calls?

y = ex1(n)

Chapter 4: Algorithm Analysis –23

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Code Evaluation #1
def ex1( n ):
count = 0
for i in range( n ):
count += i
return count

O(n)

Chapter 4: Algorithm Analysis –24

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Code Evaluation #2

def ex2( n ):
count = 0
for i in range( n ):
count += 1
for j in range( n ):
count += 1
return count

O(n)
Chapter 4: Algorithm Analysis –25
© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Code Evaluation #3

def ex3( n ):
count = 0
for i in range( n ):
for j in range( n ):
count += 1
return count

2
O(n )
Chapter 4: Algorithm Analysis –26
© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Code Evaluation #4
def ex4( n ):
count = 0
for i in range( n ):
for j in range( 25 ):
count += 1
return count

O(n)
Chapter 4: Algorithm Analysis –27
© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Code Evaluation #5
def ex5( n ):
count = 0
for i in range( n ):
for j in range( i+1 ):
count += 1
return count

2
O(n )
Chapter 4: Algorithm Analysis –28
© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Code Evaluation #6

def ex6( n ):
count = 0
i = n
while i >= 1 :
count += 1
i = i // 2
return count

O(log(n))
Chapter 4: Algorithm Analysis –29
© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Different Cases

⚫ Some algorithms have different run times for

different sets of inputs of the same size.
⚫ best case
⚫ worst case
⚫ average case

Chapter 4: Algorithm Analysis –30

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Different Cases

def findNeg( intSeq ):

n = len( intSeq )
for i in range( n ) :
if intSeq[i] < 0 :
return i
return None

L = [ 72, 4, 90, 56, 12, 67, 43, 17, 2, 86, 33 ]

p = findNeg( L )

L = [ -12, 50, 4, 67, 39, 22, 43, 2, 17, 28 ]

p = findNeg( L )

Chapter 4: Algorithm Analysis –31

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 The Python List

⚫ We used the list to implement many of our ADTs.

⚫ Their efficiency depends on the efficiency of
Python's list.

Chapter 4: Algorithm Analysis –32

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Python List: Traversal

⚫ Iterates over the contiguous elements of the

underlying array.
# Sum the elements of a list.
sum = 0
for value in valueList :
sum = sum + value

# Alternate version.
sum = 0
n = len(valueList)
for i in range( n ) :
sum = sum + valueList[i]

Chapter 4: Algorithm Analysis –33

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Python List: Allocation

⚫ Creating a non-empty list is not constant.

temp = list()
listX = [ 0 ] * n
valueList = [ 4, 8, 20, 2, 15, 89, 60, 75 ]

Chapter 4: Algorithm Analysis –34

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Python List: Appending

⚫ When space is available, the item is stored in the

next slot.

What if the underlying

array is full?

Chapter 4: Algorithm Analysis –35

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Python List: Expansion

⚫ Expanding the underlying array:

⚫ Step 1: create a new array, double the size.
⚫ Step 2: copy the items from original array to the new array.
⚫ Step 3: replace the original array with the new array.
⚫ Step 4: store the new value the next slot of the new array.

Chapter 4: Algorithm Analysis –36

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Python List: Extending

⚫ Adds the contents of a source list to the end of the

destination list.

Chapter 4: Algorithm Analysis –37

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Python List: Time-Complexities

List Operation Worst Case

v = list() O(1)
len(v) O(1)
v=[0]*n O(n)
v[i] = x O(1)
[Link](x) O(n)
[Link](w) O(n)
[Link](x) O(n)
[Link]() O(n)
traversal O(n)

Chapter 4: Algorithm Analysis –38

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Amortized Cost

⚫ Consider a sequence of n append operations:

L = list()
for i in range( 1, n+1 ):
[Link]( i )

⚫ What is the worst-case running time?

Chapter 4: Algorithm Analysis –39

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Special Case

⚫ The append() method introduces a special case.

⚫ available capacity: O(1)
⚫ expansion required: O(n)

How many times does

append require O(n) time?

Chapter 4: Algorithm Analysis –40

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Amortized Analysis

⚫ Given a sequence of operations, compute the

time-complexity by computing the average cost
over the entire sequence.
⚫ Cost per operation must be known.
⚫ Cost must vary, with
− many ops contributing little cost.
− only a few ops contributing high cost.

Chapter 4: Algorithm Analysis –41

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Aggregate Method

⚫ Determine upper bound total cost: T(n)

⚫ Calculate average cost: T(n) / n

⚫ Example: sequence of n append operations

⚫ Storage of a single item: O(1)
⚫ Expansion only occurs when (i – 1) is a power of 2.
⚫ Cost of the expansion based on current array size.

Chapter 4: Algorithm Analysis –42

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Amortized Cost

⚫ The append() operation:

⚫ worst-case time: O(n)
⚫ amortized cost: O(1)

⚫ Can only be used for a long sequence of append

operations.

Chapter 4: Algorithm Analysis –43

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 The Sparse Matrix

⚫ A matrix containing a large number of 0 elements.

⚫ Common in scientific applications.
⚫ Formal definition:
⚫ An m x n matrix that contains k non-zero elements.
⚫ Such that k << m x n.

Chapter 4: Algorithm Analysis –44

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Data Organization

⚫ The use of a 2-D array for the Matrix ADT:

⚫ Works well for general matrices.
⚫ Wastes space for large sparse matrices.

Chapter 4: Algorithm Analysis –45

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Data Organization

⚫ Use a single list and store the non-zero elements.

Chapter 4: Algorithm Analysis –46

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 SparseMatrix Class
[Link]

class SparseMatrix :
def __init__( self, numRows, numCols ):
self._numRows = numRows
self._numCols = numCols
self._elementList = list()

def numRows( self ):

return self._numRows

def numCols( self ):

return self._numCols
# ...

class _MatrixElement:
def __init__( self, row, col, value ):
[Link] = row
[Link] = col
[Link] = value
Chapter 4: Algorithm Analysis –47
© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 SparseMatrix: ScaleBy
[Link]

class SparseMatrix :
# ...
def scaleBy( self, scalar ):
for element in self._elementList :
[Link] *= scalar

Chapter 4: Algorithm Analysis –48

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Setting an Element

⚫ Set an element by row and column indices.

M = SparseMatrix(5, 8)
M[0,1] = 3
M[3,7] = 3
M[1,6] = 5

⚫ In the 2-D array implementation of the Matrix

class, this was easy.
⚫ For the SparseMatrix class, an element can not be
directly set.

Chapter 4: Algorithm Analysis –49

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Setting an Element

⚫ There are four possible conditions:

⚫ The element is not in the list.
− New value is not 0
− New value is 0
⚫ The element is in the list.
− New value is not 0.
− New value is 0.

Chapter 4: Algorithm Analysis –50

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 SparseMatrix: SetItem
[Link]

class SparseMatrix :
# ...
def __setitem__( self, ndxTuple, scalar ):
ndx = self._findPosition( ndxTuple[0], ndxTuple[1] )

if ndx is not None :

if scalar != 0.0 :
self._elementList[ndx].value = scalar
else :
self._elementList.pop( ndx )

else :
if scalar != 0.0 :
element = _MatrixElement( ndxTuple[0],
ndxTuple[1], scalar )
self._elementList.append( element )

Chapter 4: Algorithm Analysis –51

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 SparseMatrix: Find Position
[Link]

class SparseMatrix :
# ...
def _findPosition( self, row, col ):
n = len( self._elementList )
for i in range( n ) :
if row == self._elementList[i].row and \
col == self._elementList[i].col:
return i
return None

Chapter 4: Algorithm Analysis –52

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 SparseMatrix: Addition

⚫ The same add() operation can be used.

class SparseMatrix :
# ...
def __add__( self, rhsMatrix ):
for r in range( [Link]() ) :
for c in range( [Link]() ) :
newMatrix[r,c] = self[r,c] + rhsMatrix[r,c]
return newMatrix

Chapter 4: Algorithm Analysis –53

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 SparseMatrix Analysis

⚫ Assume a square n x n matrix with k << n x n.

⚫ constructor: O(1)
⚫ size: O(1)
⚫ scaleBy: O(k)
⚫ get/set item: O(k)
⚫ addition O(n2)

Chapter 4: Algorithm Analysis –54

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Faster Addition

⚫ We can improve the addition operation by only

considering the non-zero elements.

Chapter 4: Algorithm Analysis –55

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Faster Addition

Chapter 4: Algorithm Analysis –56

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Faster Addition

⚫ Requires 4 steps.
⚫ Verify the precondition.
⚫ Create a new SparseMatrix object.
⚫ Duplicate the elements of the self matrix.
⚫ Iterate over the rhs matrix elements and add them
to the new matrix.

Chapter 4: Algorithm Analysis –57

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 SparseMatrix: Faster Addition
[Link]

class SparseMatrix :
# ...
def __add__( self, rhsMatrix ):
assert [Link]() == [Link]() and \
[Link]() == [Link](), \
"Matrix sizes not compatible for the add operation."

newMatrix = SparseMatrix([Link](), [Link]())

for element in self._elementList :

dupElement = _MatrixElement([Link], [Link],
[Link])
newMatrix._elementList.append( dupElement )

for element in rhsMatrix._elementList :

value = newMatrix[ [Link], [Link] ]
value += [Link]
newMatrix[ [Link], [Link] ] = value

return newMatrix
Chapter 4: Algorithm Analysis –58
© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Faster Addition Analysis

⚫ Assume a square n x n matrix with k << n x n.

⚫ check precondition: O(1)
⚫ create new matrix: O(1)
⚫ Duplicate lhs: O(k)
⚫ Loop through rhs list: O(2k2)
− get item: O(k)
− set item: O(k)

Chapter 4: Algorithm Analysis –59

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.
 Time-Complexity Comparisons

Operation Matrix SparseMatrix

constructor O(n2) O(1)
[Link]() O(1) O(1)
[Link]() O(1) O(1)
[Link](x) O(n2) O(k)
x = m[i, j] O(1) O(k)
m[i, j] = x O(1) O(k)
r=m+t O(n2) O(k2)

Chapter 4: Algorithm Analysis –60

© 2011 John Wiley & Sons, Data Structures and Algorithms Using Python, by Rance D. Necaise.