INN701 Lecture 1
Queensland University of Technology
CRICOS No. 00213J
CAB301 Algorithms and Complexity
Lecture 2: Analysis of Algorithms
Maolin Tang
School of Computer Science
Queensland University of Technology
CRICOS No. 00213J
a university for the worldreal R
Aims of this lecture
• To introduce two ways of analysis of algorithms
– Theoretical algorithm analysis
– Empirical algorithm analysis
2
CRICOS No. 00213J
a university for the worldreal R
References
• A. Levitin. Introduction to the Design and Analysis of Algorithms.
Pearson, third edition, 2012. Sections 2.1, 2.2(O-notation only), 2.3
and 2.6, and Appendix A
3
CRICOS No. 00213J
a university for the worldreal R
Analysis of algorithms
• In computer science, analysis of algorithms is to measure the
efficiency of algorithms.
• There are two ways to measure the efficiency of algorithms
– Theoretical analysis
– Empirical analysis
4
CRICOS No. 00213J
a university for the worldreal R
Procedure of theoretical analysis of the
efficiency of an algorithm
1. Decide on the parameter(s) characterising the size of input
2. Identify the algorithm’s basic operation
3. Set up a summation formula for the number of times the basic
operation is performed in the worst scenario
4. Solve the summation formula using standard arithmetic rules
– The result is either an exact efficiency equation or identification
of the algorithm’s efficiency class in big-O notation
5
CRICOS No. 00213J
a university for the worldreal R
Size of input
• The input size depends on the data structures involved
• When dealing with compound data structures it is usually the
number of components:
– The number of items in an array
– The dimensions of a matrix
– The number of nodes or edges in a graph
• Sometimes the input size is defined by two or more parameters to
an algorithm
– The two dimensions of a matrix
– The number of nodes and the number of edges in a graph
6
CRICOS No. 00213J
a university for the worldreal R
Basic operation
• A basic operation is an operation have the most influence on the
algorithm’s total computation time:
– Key comparisons in a searching algorithm
– Numeric multiplications in a matrix multiplication algorithm
– Visits to nodes (or edges) in a graph traversal algorithm
• A basic operation may occur in more than one place in an algorithm
7
CRICOS No. 00213J
a university for the worldreal R
Example: Maximum and minimum values
ALGORITHM MaxMin2(A[0..n − 1], MaxValue, MinValue)
// Finds the maximum and minimum numbers in an
// array A of n numbers, where n ≥ 1
MaxValue ← A[0]
MinValue ← A[0]
for i ← 1 to n − 1 do
if A[i] > MaxValue
MaxValue ← A[i]
else
if A[i] < MinValue
MinValue ← A[i]
8
CRICOS No. 00213J
a university for the worldreal R
Example: Maximum and minimum values
• Input size: The length n of array A
• Basic operation: Comparison of a value with a number in the array
– This basic operation appears in two places, ‘A[i] > MaxValue’ and
‘A[i] < MinValue’
• The algorithm can perform different numbers of basic operations at
each iteration
9
CRICOS No. 00213J
a university for the worldreal R
Example: Maximum and minimum values
• The worst case is when the first array element A[0] contains the
largest number in the array, because this means the second if
statement is always performed
– In this situation the basic operation is performed twice for each
iteration of the for loop
– Thus the algorithm’s worst-case efficiency function is:
1 1
1 1
( ) 2 2 1 2( 1) 2 2
n n
worst
i i
C n n n
− −
= =
= = = − = −∑ ∑
10
CRICOS No. 00213J
a university for the worldreal R
Some frequently-used
summation manipulation rules
cai
i=l
u
∑ = c ai
i=l
u
∑
(ai ± bi )
i=l
u
∑ = ai
i=l
u
∑ ± bi
i=l
u
∑
1
i=l
u
∑ = u − l +1, l ≤ u
i
i=1
n
∑ =
n(n +1)
2
≈
1
2
n2
ik
i=1
n
∑ ≈
1
k +1
nk+1
11
Textbook - Appendix A
CRICOS No. 00213J
a university for the worldreal R
Big-O notation
• Let O(g(n)) be a class of all functions that are bounded from above
by some multiple c of g(n), for ‘large’ values of n
• If some function t(n) is in the class O(g(n)) then its worst-case
behaviour is bounded by a function with the same ‘shape’ as g(n)
• For example:
– t(n) = 4n2 + 21n + 100 ∈ O(n2)
– We can formally prove this by showing that 8n2 ≥ 4n2 + 21n + 100
for any n ≥ 9
12
CRICOS No. 00213J
a university for the worldreal R
Big-O notation
13
CRICOS No. 00213J
a university for the worldreal R
Big-O notation
• Big-O classes ignore fine detail such as multiplicative constants,
bases of logarithms and low-order terms in polynomials
• Nevertheless, they are sufficient to distinguish acceptable algorithms
from unacceptable ones
– An O(n) algorithm will outperform an O(n2) on average for large
inputs
– An O(2n) algorithm will never work on large inputs
14
CRICOS No. 00213J
a university for the worldreal R
Example: Maximum and minimum values
• The efficiency of the algorithm in big-O notation:
( ) 2 2 ( )worstC n n O n= − ∈
15
CRICOS No. 00213J
a university for the worldreal R
From efficiency function to big-O notation
• 4n2 + 2n - 100 ∈ O(n2)
• 400n2 ∈ O(n2)
• 0.01n2 ∈ O(n2)
• 3n3 + 5n2 - n + 10 ∈ O(n3)
• 2n + 100 ∈ O(n)
16
CRICOS No. 00213J
a university for the worldreal R
Example: Element uniqueness
• Consider the following algorithm:
17
CRICOS No. 00213J
a university for the worldreal R
Example: Element uniqueness
• The worst case is when all elements are unique (or when only the
last two elements are equal)
– The basic operation is done once in the innermost loop body
– The innermost loop occurs for j equal to i + 1 to n − 1, inclusive:
– Outermost loop is performed for i equal to 0 to n − 2, inclusive:
– Thus the algorithm’s worst-case efficiency is:
1
1
1 ( 1) ( 1) 1 1
n
j i
n i n i
−
= +
= − − + + = − −∑
2 2( 1) 1 1( ) ( )
2 2 2worst
n n
C n n n O n
−
= = − ∈
18
2 1
0 1
( 1)
( 1 ) ( 1) ( 2) 1
2
n n
i i
n n
n i n n i
− −
= =
−
− − = − + − + + = =∑ ∑
cai
i=l
u
∑ = c ai
i=l
u
∑
(ai ± bi )
i=l
u
∑ = ai
i=l
u
∑ ± bi
i=l
u
∑
1
i=l
u
∑ = u − l +1, l ≤ u
i
i=1
n
∑ =
n(n +1)
2
≈
1
2
n2
ik
i=1
n
∑ ≈
1
k +1
nk+1
CRICOS No. 00213J
a university for the worldreal R
Deriving efficiency classes
from algorithm structure
• With experience it is possible to identify an algorithm’s efficiency
class from the pseudocode’s structure
– Assignments v ← E are usually assumed to take constant time,
i.e., to belong to class O(1)
– The efficiency class of most compound statements can then be
identified by inspection of the pseudocode
– However, in tricky cases we may still need to produce
summations or recurrence relations to determine the efficiency
class accurately
19
CRICOS No. 00213J
a university for the worldreal R
Iterative code: Independent loops
• For a loop that iterates a fixed number of times, the loop body is
executed in direct proportion to the loop variable’s range
for j ← 0 to n − 1 do
x ← x + 1 // basic operation
• Nested loops are analysed from the innermost to the outermost
for i ← 0 to n − 1 do
for j ← 0 to n − 1 do
x ← x + 1
O(n)
O(n)
O(n2)
20
CRICOS No. 00213J
a university for the worldreal R
Sequential composition
• For a sequence of statements S1, S2, …, Sk the total efficiency is the
sum of the individual statements’ efficiencies
• However, the overall order of growth is dominated by the largest
polynomial term for any individual statement
for i ← 0 to n − 1 do
x ← x + 1
for i ← 0 to n − 1 do
for j ← 0 to n − 1 do
x ← x + 1
O(n)
O(n2)
O(n2)
21
CRICOS No. 00213J
a university for the worldreal R
Conditional statements
• The worst-case order of growth for a conditional statement is the
largest of any of its alternatives
if B
S1
else
S2
O(m)
O(n)
O(max(m, n))
22
CRICOS No. 00213J
a university for the worldreal R
Iterative code: Dependent loops
• Where loop variables depend on one another we usually have to
produce a summation to accurately identify the efficiency class
for i ← 0 to n − 1 do
for j ← i to n − 1 do
x ← x + 1
because
O(n − i) O(n
2)
23
1 1
2 2
0 0 1
( 1) 1 1
(( 1) 1) ( ) ( 1) 1 ( )
2 2 2
n n n
i i i
n n
n i n i n n i n n O n
− −
= = =
+
− − + = − = + − + + = = = + ∈∑ ∑ ∑
cai
i=l
u
∑ = c ai
i=l
u
∑
(ai ± bi )
i=l
u
∑ = ai
i=l
u
∑ ± bi
i=l
u
∑
1
i=l
u
∑ = u − l +1, l ≤ u
i
i=1
n
∑ =
n(n +1)
2
≈
1
2
n2
ik
i=1
n
∑ ≈
1
k +1
nk+1
CRICOS No. 00213J
a university for the worldreal R
Iterative code: Uneven steps
• Loops where the size of the steps decreases (or increases) by a
power have a logarithmic (or exponential) growth
i ← 1
while i < n do
for j ← 0 to n − 1 do
x ← x + 1
i ← i ∗ 2
because the inner loop’s body is always performed n times and
when n equals 2k the outer loop’s body is performed k = log2 n times
with i equal to 1, 2, 4, 8, 16, …, 2k−1 (or, equivalently, 20, 21, 22, 23, 24,
…, 2k−1)
O(1)
O(n)
O(n) O(n log n)
2
1
log ( log )
k
x
n n k n n O n n
=
= ⋅ = ⋅ ∈∑
24
CRICOS No. 00213J
a university for the worldreal R
Iterative code: Balanced loops
• In some situations two nested loops will counterbalance one
another to produce an ‘obvious’ result in a non-obvious way
i ← 1
while i < n do
for j ← 1 to i do
x ← x + 1
i ← i ∗ 2
because if n equals 2k then the inner loop is performed k = log2 n
times with i equal to 1, 2, 4, 8, 16, …, 2k−1 and the basic operation is
performed 20 + 21 + 22 + 23 + 24 + … + 2k−1 times in total
O(i)
O(1)
O(i) O(n)
( )
1
1 1
0
2 2 1 2 1 1 ( )
k
kx k
x
n O n
−
− +
=
= − = − = − ∈∑
25
cai
i=l
u
∑ = c ai
i=l
u
∑
(ai ± bi )
i=l
u
∑ = ai
i=l
u
∑ ± bi
i=l
u
∑
1
i=l
u
∑ = u − l +1, l ≤ u
i
i=1
n
∑ =
n(n +1)
2
≈
1
2
n2
ik
i=1
n
∑ ≈
1
k +1
nk+1
CAB301 Algorithms and Complexity��Lecture 2: Analysis of Algorithms
Aims of this lecture
References
Analysis of algorithms
Procedure of theoretical analysis of the efficiency of an algorithm
Size of input
Basic operation
Example: Maximum and minimum values
Example: Maximum and minimum values
Example: Maximum and minimum values
Some frequently-used�summation manipulation rules
Big-O notation
Big-O notation
Big-O notation
Example: Maximum and minimum values
From efficiency function to big-O notation
Example: Element uniqueness
Example: Element uniqueness
Deriving efficiency classes�from algorithm structure
Iterative code: Independent loops
Sequential composition
Conditional statements
Iterative code: Dependent loops
Iterative code: Uneven steps
Iterative code: Balanced loops