CS计算机代考程序代写 data structure AI algorithm COSC1285/2123: Algorithms & Analysis - Algorithmic Analysis

COSC1285/2123: Algorithms & Analysis – Algorithmic Analysis

COSC1285/2123: Algorithms & Analysis
Algorithmic Analysis

Hoang MIT University
Email : sonhoang. .au

Lecture 2

(RMIT University) Algorithmic Analysis Lecture 2 1 / 74

Outline

1 Overview

2 Fundamentals

3 Asymptotic Complexity

4 Analysing Non-recursive Algorithms

5 Analysing Recursive Algorithms

6 Empirical Analysis

7 Rule of thumb Estimation of Complexity

8 Summary
(RMIT University) Algorithmic Analysis Lecture 2 2 / 74

Overview

1 Overview

2 Fundamentals

3 Asymptotic Complexity

4 Analysing Non-recursive Algorithms

5 Analysing Recursive Algorithms

6 Empirical Analysis

7 Rule of thumb Estimation of Complexity

8 Summary
(RMIT University) Algorithmic Analysis Lecture 2 3 / 74

Overview

Levitin – The design and analysis of algorithms
This week we will be covering the material from Chapter 2.

Learning outcomes:
• Understand why it is important to be able to compare the

complexiy of algorithms.
• Be able to:

• measure complexity of algorithms and compare complexity classes.
• analysis of non-recursive algorithms.
• analysis of recursive algorithms.

• Be able to perform empirical analysis of algorithms.

(RMIT University) Algorithmic Analysis Lecture 2 4 / 74

Example: Which is faster?

Scenario: You work for a small medicine
stocker. Your boss comes and asks your
opinion on which of two approaches is faster
for employees to search over an unordered
set of medicines (strings).

Question: Which of the following two approaches will you tell your
boss is faster?

• Solution A: Sequential search.
• Solution B: Sort then search.

(RMIT University) Algorithmic Analysis Lecture 2 5 / 74

Example: Which is faster?

Scenario: You work for a small medicine
stocker. Your boss comes and asks your
opinion on which of two approaches is faster
for employees to search over an unordered
set of medicines (strings).

Question: Which of the following two approaches will you tell your
boss is faster?

• Solution A: Sequential search.
• Solution B: Sort then search.

(RMIT University) Algorithmic Analysis Lecture 2 5 / 74

Example: Which is faster?

Scenario: You work for a small medicine
stocker. Your boss comes and asks your
opinion on which of two approaches is faster
for employees to search over an unordered
set of medicines (strings).

Question: Which of the following two approaches will you tell your
boss is faster?

• Solution A: Sequential search.

• Solution B: Sort then search.

(RMIT University) Algorithmic Analysis Lecture 2 5 / 74

Example: Which is faster?

Scenario: You work for a small medicine
stocker. Your boss comes and asks your
opinion on which of two approaches is faster
for employees to search over an unordered
set of medicines (strings).

Question: Which of the following two approaches will you tell your
boss is faster?

• Solution A: Sequential search.
• Solution B: Sort then search.

(RMIT University) Algorithmic Analysis Lecture 2 5 / 74

Which is faster?

• In this lecture, we look at the ways of estimating the running time
of a program and how to compare the running times of two
programs without ever implementing them.

• It is vital to analyse the resource use of an algorithm, well before it
is implemented and deployed.

Space is also important but we focus on time in this course.

(RMIT University) Algorithmic Analysis Lecture 2 6 / 74

Which is faster?

• In this lecture, we look at the ways of estimating the running time
of a program and how to compare the running times of two
programs without ever implementing them.
• It is vital to analyse the resource use of an algorithm, well before it

is implemented and deployed.

Space is also important but we focus on time in this course.

(RMIT University) Algorithmic Analysis Lecture 2 6 / 74

Which is faster?

is implemented and deployed.

Space is also important but we focus on time in this course.

(RMIT University) Algorithmic Analysis Lecture 2 6 / 74

Overview

1 Overview

2 Fundamentals

3 Asymptotic Complexity

4 Analysing Non-recursive Algorithms

5 Analysing Recursive Algorithms

6 Empirical Analysis

7 Rule of thumb Estimation of Complexity

8 Summary
(RMIT University) Algorithmic Analysis Lecture 2 7 / 74

Theoretical Analysis of Time Efficiency

How to estimate the running time of an algorithm?

Idea: An algorithm consists of some operations executed a number of
times.

Hence, an estimate of the running time/time efficiency of an algorithm
can be obtained from determining these operations, how long to
execute them, and the number of times they are executed.

These operations are called basic operations and the number of
times is based on the input size of the problem.

(RMIT University) Algorithmic Analysis Lecture 2 8 / 74

Theoretical Analysis of Time Efficiency

How to estimate the running time of an algorithm?

Idea: An algorithm consists of some operations executed a number of
times.

Hence, an estimate of the running time/time efficiency of an algorithm
can be obtained from determining these operations, how long to
execute them, and the number of times they are executed.

These operations are called basic operations and the number of
times is based on the input size of the problem.

(RMIT University) Algorithmic Analysis Lecture 2 8 / 74

Theoretical Analysis of Time Efficiency

How to estimate the running time of an algorithm?

Idea: An algorithm consists of some operations executed a number of
times.

Hence, an estimate of the running time/time efficiency of an algorithm
can be obtained from determining these operations, how long to
execute them, and the number of times they are executed.

These operations are called basic operations and the number of
times is based on the input size of the problem.

(RMIT University) Algorithmic Analysis Lecture 2 8 / 74

Running example: an

This algorithm computes an:

// INPUT : a, n
// OUTPUT : s = an

1: set s = 1
2: for i = 1 to n do
3: s = s ∗ a
4: end for
5: return s

(RMIT University) Algorithmic Analysis Lecture 2 9 / 74

Basic Operation

What is a basic operation?

• Operation(s) that contribute most towards the total running time.
• Examples: compare, add, multiply, divide or assignment.
• Typically the operation most frequently executed, although

dependent on the time of each operation.

What is the basic operation of our example algorithm?

// INPUT : a, n
// OUTPUT : s = an

1: set s = 1
2: for i = 1 to n do
3: s = s ∗ a
4: end for
5: return s

(RMIT University) Algorithmic Analysis Lecture 2 10 / 74

Basic Operation

What is a basic operation?
• Operation(s) that contribute most towards the total running time.

• Examples: compare, add, multiply, divide or assignment.
• Typically the operation most frequently executed, although

dependent on the time of each operation.

What is the basic operation of our example algorithm?

// INPUT : a, n
// OUTPUT : s = an

1: set s = 1
2: for i = 1 to n do
3: s = s ∗ a
4: end for
5: return s

(RMIT University) Algorithmic Analysis Lecture 2 10 / 74

Basic Operation

What is a basic operation?
• Operation(s) that contribute most towards the total running time.
• Examples: compare, add, multiply, divide or assignment.

• Typically the operation most frequently executed, although
dependent on the time of each operation.

What is the basic operation of our example algorithm?

// INPUT : a, n
// OUTPUT : s = an

1: set s = 1
2: for i = 1 to n do
3: s = s ∗ a
4: end for
5: return s

(RMIT University) Algorithmic Analysis Lecture 2 10 / 74

Basic Operation

What is a basic operation?
• Operation(s) that contribute most towards the total running time.
• Examples: compare, add, multiply, divide or assignment.
• Typically the operation most frequently executed, although

dependent on the time of each operation.

What is the basic operation of our example algorithm?

// INPUT : a, n
// OUTPUT : s = an

1: set s = 1
2: for i = 1 to n do
3: s = s ∗ a
4: end for
5: return s

(RMIT University) Algorithmic Analysis Lecture 2 10 / 74

Basic Operation

dependent on the time of each operation.

What is the basic operation of our example algorithm?

// INPUT : a, n
// OUTPUT : s = an

1: set s = 1
2: for i = 1 to n do
3: s = s ∗ a
4: end for
5: return s

(RMIT University) Algorithmic Analysis Lecture 2 10 / 74

Input Size

What is the input size?
• More of a characteristic of the problem, “Size of the problem”.

• E.g., searching through an array of size n, the input size is n.
• We want to estimate the running time of an algorithm in terms of

the problem, not in absolute terms.
• When analysing algorithms, we state the number of times that the

basic operation is executed in terms of the input size.

What is the input size of our example algorithm?

// INPUT : a, n
// OUTPUT : s = an

1: set s = 1
2: for i = 1 to n do
3: s = s ∗ a
4: end for
5: return s

(RMIT University) Algorithmic Analysis Lecture 2 11 / 74

Input Size

What is the input size?
• More of a characteristic of the problem, “Size of the problem”.
• E.g., searching through an array of size n, the input size is n.

• We want to estimate the running time of an algorithm in terms of
the problem, not in absolute terms.
• When analysing algorithms, we state the number of times that the

basic operation is executed in terms of the input size.

What is the input size of our example algorithm?

// INPUT : a, n
// OUTPUT : s = an

1: set s = 1
2: for i = 1 to n do
3: s = s ∗ a
4: end for
5: return s

(RMIT University) Algorithmic Analysis Lecture 2 11 / 74

Input Size

What is the input size?
• More of a characteristic of the problem, “Size of the problem”.
• E.g., searching through an array of size n, the input size is n.
• We want to estimate the running time of an algorithm in terms of

the problem, not in absolute terms.

• When analysing algorithms, we state the number of times that the
basic operation is executed in terms of the input size.

What is the input size of our example algorithm?

// INPUT : a, n
// OUTPUT : s = an

1: set s = 1
2: for i = 1 to n do
3: s = s ∗ a
4: end for
5: return s

(RMIT University) Algorithmic Analysis Lecture 2 11 / 74

Input Size

the problem, not in absolute terms.
• When analysing algorithms, we state the number of times that the

basic operation is executed in terms of the input size.

What is the input size of our example algorithm?

// INPUT : a, n
// OUTPUT : s = an

1: set s = 1
2: for i = 1 to n do
3: s = s ∗ a
4: end for
5: return s

(RMIT University) Algorithmic Analysis Lecture 2 11 / 74

Input Size

the problem, not in absolute terms.
• When analysing algorithms, we state the number of times that the

basic operation is executed in terms of the input size.

What is the input size of our example algorithm?

// INPUT : a, n
// OUTPUT : s = an

1: set s = 1
2: for i = 1 to n do
3: s = s ∗ a
4: end for
5: return s

(RMIT University) Algorithmic Analysis Lecture 2 11 / 74

More examples of basic operation and input size

Problem Type Basic Operation Input Size

Iterating through
an array, of size
n, to print its
contents

? n

Iterating through
an n× n matrix of
integers, to find a
given integer

Comparison ?

(RMIT University) Algorithmic Analysis Lecture 2 12 / 74

Theoretical Analysis of Time Efficiency

With the basic operation and input size, how do we estimate the
running time of an algorithm?

Running time approximately equal to time to execute a basic operation
× number of basic operations

t(n) ≈ cop × C(n)
• t(n) is the running time.
• n is the input size.
• cop is the execution time for a basic operation.
• C(n) is the number of times the basic operation is executed.

(RMIT University) Algorithmic Analysis Lecture 2 13 / 74

Theoretical Analysis of Time Efficiency

With the basic operation and input size, how do we estimate the
running time of an algorithm?

Running time approximately equal to time to execute a basic operation
× number of basic operations

t(n) ≈ cop × C(n)
• t(n) is the running time.
• n is the input size.
• cop is the execution time for a basic operation.
• C(n) is the number of times the basic operation is executed.

(RMIT University) Algorithmic Analysis Lecture 2 13 / 74

Theoretical Analysis of Time Efficiency

With the basic operation and input size, how do we estimate the
running time of an algorithm?

Running time approximately equal to time to execute a basic operation
× number of basic operations

t(n) ≈ cop × C(n)
• t(n) is the running time.
• n is the input size.
• cop is the execution time for a basic operation.
• C(n) is the number of times the basic operation is executed.

(RMIT University) Algorithmic Analysis Lecture 2 13 / 74

Estimating algorithm for an

What is the theoretical running time for our algorithm for computing an?

Recall: t(n) ≈ cop × C(n)

// INPUT : a, n
// OUTPUT : s = an

1: set s = 1
2: for i = 1 to n do
3: s = s ∗ a
4: end for
5: return s

Answer: C(n) = n (number of times basic op. executed)

t(n) ≈ cop × C(n) = cop × n

(RMIT University) Algorithmic Analysis Lecture 2 14 / 74

Estimating algorithm for an

What is the theoretical running time for our algorithm for computing an?

Recall: t(n) ≈ cop × C(n)

// INPUT : a, n
// OUTPUT : s = an

1: set s = 1
2: for i = 1 to n do
3: s = s ∗ a
4: end for
5: return s

Answer: C(n) = n (number of times basic op. executed)

t(n) ≈ cop × C(n) = cop × n

(RMIT University) Algorithmic Analysis Lecture 2 14 / 74

Estimating algorithm for an

What is the theoretical running time for our algorithm for computing an?

Recall: t(n) ≈ cop × C(n)

// INPUT : a, n
// OUTPUT : s = an

1: set s = 1
2: for i = 1 to n do
3: s = s ∗ a
4: end for
5: return s

Answer: C(n) = n (number of times basic op. executed)

t(n) ≈ cop × C(n) = cop × n

(RMIT University) Algorithmic Analysis Lecture 2 14 / 74

Example: Searching for a key in n items using
Sequential Search

ALGORITHM SequentialSearch (A[0 . . . n − 1],K )
// INPUT : An array A of length n and a search key K .
// OUTPUT : The index of the first element of A which matches K or n
(length of A) otherwise.

1: set i = 0
2: while i < n and A[i] 6= K do 3: set i = i + 1 4: end while 5: return i (RMIT University) Algorithmic Analysis Lecture 2 15 / 74 Example: Searching for a key in n items using Sequential Search ALGORITHM SequentialSearch (A[0 . . . n − 1],K ) // INPUT : An array A of length n and a search key K . // OUTPUT : The index of the first element of A which matches K or n (length of A) otherwise. 1: set i = 0 2: while i < n and A[i] 6= K do 3: set i = i + 1 4: end while 5: return i • Basic Operation? comparison, addition, assignment (any of these are okay) • Input size? n (RMIT University) Algorithmic Analysis Lecture 2 16 / 74 Example: Searching for a key in n items using Sequential Search ALGORITHM SequentialSearch (A[0 . . . n − 1],K ) // INPUT : An array A of length n and a search key K . // OUTPUT : The index of the first element of A which matches K or n (length of A) otherwise. 1: set i = 0 2: while i < n and A[i] 6= K do 3: set i = i + 1 4: end while 5: return i • Basic Operation? comparison, addition, assignment (any of these are okay) • Input size? n (RMIT University) Algorithmic Analysis Lecture 2 16 / 74 Example: Searching for a key in n items using Sequential Search ALGORITHM SequentialSearch (A[0 . . . n − 1],K ) // INPUT : An array A of length n and a search key K . // OUTPUT : The index of the first element of A which matches K or n (length of A) otherwise. 1: set i = 0 2: while i < n and A[i] 6= K do 3: set i = i + 1 4: end while 5: return i • Basic Operation? comparison, addition, assignment (any of these are okay) • Input size? n (RMIT University) Algorithmic Analysis Lecture 2 16 / 74 Example: Searching for a key in n items using Sequential Search ALGORITHM SequentialSearch (A[0 . . . n − 1],K ) // INPUT : An array A of length n and a search key K . // OUTPUT : The index of the first element of A which matches K or n (length of A) otherwise. 1: set i = 0 2: while i < n and A[i] 6= K do 3: set i = i + 1 4: end while 5: return i • Basic Operation? comparison, addition, assignment (any of these are okay) • Input size? n (RMIT University) Algorithmic Analysis Lecture 2 16 / 74 Example: Searching for a key in n items using Sequential Search What is the theoretical running time for Sequential Search? Recall: t(n) ≈ cop × C(n) ALGORITHM SequentialSearch (A[0 . . . n − 1],K ) // INPUT : An array A of length n and a search key K . // OUTPUT : The index of the first element of A which matches K or n (length of A) otherwise. 1: set i = 0 2: while i < n and A[i] 6= K do 3: set i = i + 1 4: end while 5: return i What is C(n), the number of times the basic operation is executed? (RMIT University) Algorithmic Analysis Lecture 2 17 / 74 Runtime Complexity • Worst Case - Given an input of n items, what is the maximum running time for any possible input? • - Given an input of n items, what is the minimum running time for any possible input? • Average Case - Given an input of n items, what is the average running time across all possible inputs? NOTE : Average Case is not the average of the worst and best case. Rather, it is the average performance across all possible inputs. (RMIT University) Algorithmic Analysis Lecture 2 18 / 74 Runtime Complexity • Worst Case - Given an input of n items, what is the maximum running time for any possible input? • - Given an input of n items, what is the minimum running time for any possible input? • Average Case - Given an input of n items, what is the average running time across all possible inputs? NOTE : Average Case is not the average of the worst and best case. Rather, it is the average performance across all possible inputs. (RMIT University) Algorithmic Analysis Lecture 2 18 / 74 Runtime Complexity • Worst Case - Given an input of n items, what is the maximum running time for any possible input? • - Given an input of n items, what is the minimum running time for any possible input? • Average Case - Given an input of n items, what is the average running time across all possible inputs? NOTE : Average Case is not the average of the worst and best case. Rather, it is the average performance across all possible inputs. (RMIT University) Algorithmic Analysis Lecture 2 18 / 74 Runtime Complexity • Worst Case - Given an input of n items, what is the maximum running time for any possible input? • - Given an input of n items, what is the minimum running time for any possible input? • Average Case - Given an input of n items, what is the average running time across all possible inputs? NOTE : Average Case is not the average of the worst and best case. Rather, it is the average performance across all possible inputs. (RMIT University) Algorithmic Analysis Lecture 2 18 / 74 Sequential Search ALGORITHM SequentialSearch (A[0 . . . n − 1],K ) 1: set i = 0 2: while i < n and A[i] 6= K do 3: set i = i + 1 4: end while 5: return i Best-case : The best case input is when the item being searched for is the first item in the list, so Cb(n) = 1. Worst-case : The worst case input is when the item being searched for is not present in the list, so Cw (n) = n (RMIT University) Algorithmic Analysis Lecture 2 19 / 74 Sequential Search Average-case : What does average-case mean? • Recall: average across all possible inputs – how to analyse this? • Typically not straight forward. Sequential Search Example: • How often do we search for items in the array? • Where in the array do we find the item? 1st, 2nd, . . ., last position? • How often do we search for items not in the array? (RMIT University) Algorithmic Analysis Lecture 2 20 / 74 Sequential Search Average-case : What does average-case mean? • Recall: average across all possible inputs – how to analyse this? • Typically not straight forward. Sequential Search Example: • How often do we search for items in the array? • Where in the array do we find the item? 1st, 2nd, . . ., last position? • How often do we search for items not in the array? (RMIT University) Algorithmic Analysis Lecture 2 20 / 74 Sequential Search Average-case Analysis : Skipping a few steps (notes of full derivation available on Canvas) and p is the probability of a successful search. Cavg(n) = p(n + 1) 2 + n(1− p) If p = 1, then Cavg(n) = (n + 1)/2. If p = 0, then Cavg(n) = n. (RMIT University) Algorithmic Analysis Lecture 2 21 / 74 Summary for this part • Input size, basic operation • Time complexity estimate using input size and basic operation • Best, worst, and average cases (RMIT University) Algorithmic Analysis Lecture 2 22 / 74 Overview 1 Overview 2 Fundamentals 3 Asymptotic Complexity 4 Analysing Non-recursive Algorithms 5 Analysing Recursive Algorithms 6 Empirical Analysis 7 Rule of thumb Estimation of Complexity 8 Summary (RMIT University) Algorithmic Analysis Lecture 2 23 / 74 Asymptotic Complexity Problem: • We now have a way to analyse the running time (aka time complexity) of an algorithm, but every algorithms have their own time complexities. How to compare in a meaningful way? (RMIT University) Algorithmic Analysis Lecture 2 24 / 74 Asymptotic Complexity Consider the running times estimates of two algorithms: Algorithm 1: T1(n) = 5.1n Algorithm 2: T2(n) = 5.2n Similar timing profiles as n grows? What about the following?: Algorithm 3: T3(n) = 5.1n 2 Algorithm 4: T4(n) = 5.2n 2 (RMIT University) Algorithmic Analysis Lecture 2 25 / 74 Asymptotic Complexity Consider the running times estimates of two algorithms: Algorithm 1: T1(n) = 5.1n Algorithm 2: T2(n) = 5.2n Similar timing profiles as n grows? What about the following?: Algorithm 3: T3(n) = 5.1n 2 Algorithm 4: T4(n) = 5.2n 2 (RMIT University) Algorithmic Analysis Lecture 2 25 / 74 Asymptotic Complexity Consider the running times estimates of two algorithms: Algorithm 1: T1(n) = 5.1n Algorithm 2: T2(n) = 5.2n Similar timing profiles as n grows? What about the following?: Algorithm 3: T3(n) = 5.1n 2 Algorithm 4: T4(n) = 5.2n 2 (RMIT University) Algorithmic Analysis Lecture 2 25 / 74 Asymptotic Complexity Problem: • We now have a way to analyse the running time (aka time complexity) of an algorithm, but every algorithms have their own time complexities. How to compare in a meaningful way? Solution: • Group them into equivalence classes (for easier comparison and understanding), with respect to the input size. • Focus of this part, asymptotic complexity and equivalence classes. (RMIT University) Algorithmic Analysis Lecture 2 26 / 74 Asymptotic Complexity - bounds Warning: Some (mathematical) definitions coming up! Idea: Use bounds and asymptotic complexity (as n becomes large, what is the dominant term contributing to the running time (t(n))?) (RMIT University) Algorithmic Analysis Lecture 2 27 / 74 Asymptotic Complexity - bounds Warning: Some (mathematical) definitions coming up! Idea: Use bounds and asymptotic complexity (as n becomes large, what is the dominant term contributing to the running time (t(n))?) (RMIT University) Algorithmic Analysis Lecture 2 27 / 74 Asymptotic Complexity, Upper bounds Definition: Given a function t(n) (the running time of an algorithm): • Let c × g(n) be a function that is an upper bound on t(n) for some c > 0 and for “large” n.

(RMIT University) Algorithmic Analysis Lecture 2 28 / 74

Asymptotic Complexity, Upper bounds

Definition: Given a function t(n) (the running time of an algorithm):
• Let c × g(n) be a function that is an upper bound on t(n) for some

c > 0 and for “large” n.

(RMIT University) Algorithmic Analysis Lecture 2 28 / 74

Upper bounds Examples

0 50 100 150 200 250 300

0
2

0
0

0
6

0
0

0
1

0
0

T
(n

)

(RMIT University) Algorithmic Analysis Lecture 2 29 / 74

Asymptotic Complexity, O(n)

Rather than talking about individual upper bounds for each running
time function, we seek to group them into equivalence classes that
describe their order of growth.

Big-O notation, O(n): Given a function t(n),
• Informally: t(n) ∈ O(g(n)) means g(n) is a function that, as n

increases, provides an upper bound for t(n).
• Formally: t(n) ∈ O(g(n)), if g(n) is a function and c × g(n) is an

upper bound on t(n) for some c > 0 and for “large” n.

E.g., if t(n) = 5.1n,
• g(n) = n
• g(n) = 0.001n − 6
• g(n) = n2

What g(n) to use if t(n) = 5.2n? Any of the above g(n) functions are
possible!

(RMIT University) Algorithmic Analysis Lecture 2 30 / 74

Asymptotic Complexity, O(n)

Rather than talking about individual upper bounds for each running
time function, we seek to group them into equivalence classes that
describe their order of growth.

Big-O notation, O(n): Given a function t(n),
• Informally: t(n) ∈ O(g(n)) means g(n) is a function that, as n

increases, provides an upper bound for t(n).
• Formally: t(n) ∈ O(g(n)), if g(n) is a function and c × g(n) is an

upper bound on t(n) for some c > 0 and for “large” n.

E.g., if t(n) = 5.1n,
• g(n) = n
• g(n) = 0.001n − 6
• g(n) = n2

What g(n) to use if t(n) = 5.2n? Any of the above g(n) functions are
possible!

(RMIT University) Algorithmic Analysis Lecture 2 30 / 74

Asymptotic Complexity, O(n)

Rather than talking about individual upper bounds for each running
time function, we seek to group them into equivalence classes that
describe their order of growth.

Big-O notation, O(n): Given a function t(n),
• Informally: t(n) ∈ O(g(n)) means g(n) is a function that, as n

increases, provides an upper bound for t(n).
• Formally: t(n) ∈ O(g(n)), if g(n) is a function and c × g(n) is an

upper bound on t(n) for some c > 0 and for “large” n.

E.g., if t(n) = 5.1n,
• g(n) = n

• g(n) = 0.001n − 6
• g(n) = n2

What g(n) to use if t(n) = 5.2n? Any of the above g(n) functions are
possible!

(RMIT University) Algorithmic Analysis Lecture 2 30 / 74

Asymptotic Complexity, O(n)

Rather than talking about individual upper bounds for each running
time function, we seek to group them into equivalence classes that
describe their order of growth.

Big-O notation, O(n): Given a function t(n),
• Informally: t(n) ∈ O(g(n)) means g(n) is a function that, as n

increases, provides an upper bound for t(n).
• Formally: t(n) ∈ O(g(n)), if g(n) is a function and c × g(n) is an

upper bound on t(n) for some c > 0 and for “large” n.

E.g., if t(n) = 5.1n,
• g(n) = n
• g(n) = 0.001n − 6

• g(n) = n2

What g(n) to use if t(n) = 5.2n? Any of the above g(n) functions are
possible!

(RMIT University) Algorithmic Analysis Lecture 2 30 / 74

Asymptotic Complexity, O(n)

Rather than talking about individual upper bounds for each running
time function, we seek to group them into equivalence classes that
describe their order of growth.

Big-O notation, O(n): Given a function t(n),
• Informally: t(n) ∈ O(g(n)) means g(n) is a function that, as n

increases, provides an upper bound for t(n).
• Formally: t(n) ∈ O(g(n)), if g(n) is a function and c × g(n) is an

upper bound on t(n) for some c > 0 and for “large” n.

E.g., if t(n) = 5.1n,
• g(n) = n
• g(n) = 0.001n − 6
• g(n) = n2

What g(n) to use if t(n) = 5.2n? Any of the above g(n) functions are
possible!

(RMIT University) Algorithmic Analysis Lecture 2 30 / 74

Asymptotic Complexity, O(n)

Rather than talking about individual upper bounds for each running
time function, we seek to group them into equivalence classes that
describe their order of growth.

Big-O notation, O(n): Given a function t(n),
• Informally: t(n) ∈ O(g(n)) means g(n) is a function that, as n

increases, provides an upper bound for t(n).
• Formally: t(n) ∈ O(g(n)), if g(n) is a function and c × g(n) is an

upper bound on t(n) for some c > 0 and for “large” n.

E.g., if t(n) = 5.1n,
• g(n) = n
• g(n) = 0.001n − 6
• g(n) = n2

What g(n) to use if t(n) = 5.2n? Any of the above g(n) functions are
possible!

(RMIT University) Algorithmic Analysis Lecture 2 30 / 74

Asymptotic Complexity, O(n)

Rather than talking about individual upper bounds for each running
time function, we seek to group them into equivalence classes that
describe their order of growth.

Big-O notation, O(n): Given a function t(n),
• Informally: t(n) ∈ O(g(n)) means g(n) is a function that, as n

increases, provides an upper bound for t(n).
• Formally: t(n) ∈ O(g(n)), if g(n) is a function and c × g(n) is an

upper bound on t(n) for some c > 0 and for “large” n.

E.g., if t(n) = 5.1n,
• g(n) = n
• g(n) = 0.001n − 6
• g(n) = n2

What g(n) to use if t(n) = 5.2n?

Any of the above g(n) functions are
possible!

(RMIT University) Algorithmic Analysis Lecture 2 30 / 74

Asymptotic Complexity, O(n)

Rather than talking about individual upper bounds for each running
time function, we seek to group them into equivalence classes that
describe their order of growth.

Big-O notation, O(n): Given a function t(n),
• Informally: t(n) ∈ O(g(n)) means g(n) is a function that, as n

increases, provides an upper bound for t(n).
• Formally: t(n) ∈ O(g(n)), if g(n) is a function and c × g(n) is an

upper bound on t(n) for some c > 0 and for “large” n.

E.g., if t(n) = 5.1n,
• g(n) = n
• g(n) = 0.001n − 6
• g(n) = n2

What g(n) to use if t(n) = 5.2n? Any of the above g(n) functions are
possible!

(RMIT University) Algorithmic Analysis Lecture 2 30 / 74

Common Equivalence Classes

Previous slide, we had multiple upper bounds. But we can in fact group
them to a smaller number.

First we look at common equivalence classes:
• Constant – O(1) : Access array element
• Logarithmic – O(log n) : Binary search
• Linear – O(n) : Link list search
• Linearithmic (Supralinear) – O(n log n) : Merge Sorting
• Quadratic – O(n2) : Selection Sorting
• Exponential – O(2n) : Generating all subsets
• Factorial – O(n!) : Generating all permutations

(RMIT University) Algorithmic Analysis Lecture 2 31 / 74

Common Equivalence Classes

Previous slide, we had multiple upper bounds. But we can in fact group
them to a smaller number.

(RMIT University) Algorithmic Analysis Lecture 2 31 / 74

Common Complexity Bounds

1 5 10 50 100 500 1000

1
10

10
0

10
00

T
(n

)
constant
logarithmic
linear
linearithmic
quadratic
exponential
factorial

(RMIT University) Algorithmic Analysis Lecture 2 32 / 74

Asymptotic Complexity

Recall: We want to find equivalence function class that upper bounds
different t(n).

But we might be given an upper bound g(n) that isn’t quite in the form
of the equivalence classes. How to get the equivalence classes?

Adhere to the following guidelines:
• Do not include constants (e.g., omit ’-6’ in 0.01n − 6 to become

0.01n).
• Omit all the lower order terms (e.g., n3 + n2 + n, we simplify to n3).
• Omit the coefficient of the highest-order term (e.g., 0.01n

becomes n).
Returning to previous example, we can write the two upper bounds
O(0.01n − 6) and O(n) as O(n).

(RMIT University) Algorithmic Analysis Lecture 2 33 / 74

Asymptotic Complexity

Recall: We want to find equivalence function class that upper bounds
different t(n).

But we might be given an upper bound g(n) that isn’t quite in the form
of the equivalence classes. How to get the equivalence classes?

Adhere to the following guidelines:
• Do not include constants (e.g., omit ’-6’ in 0.01n − 6 to become

0.01n).
• Omit all the lower order terms (e.g., n3 + n2 + n, we simplify to n3).
• Omit the coefficient of the highest-order term (e.g., 0.01n

becomes n).
Returning to previous example, we can write the two upper bounds
O(0.01n − 6) and O(n) as O(n).

(RMIT University) Algorithmic Analysis Lecture 2 33 / 74

Asymptotic Complexity

Recall: We want to find equivalence function class that upper bounds
different t(n).

But we might be given an upper bound g(n) that isn’t quite in the form
of the equivalence classes. How to get the equivalence classes?

Adhere to the following guidelines:
• Do not include constants (e.g., omit ’-6’ in 0.01n − 6 to become

0.01n).
• Omit all the lower order terms (e.g., n3 + n2 + n, we simplify to n3).
• Omit the coefficient of the highest-order term (e.g., 0.01n

becomes n).

Returning to previous example, we can write the two upper bounds
O(0.01n − 6) and O(n) as O(n).

(RMIT University) Algorithmic Analysis Lecture 2 33 / 74

Asymptotic Complexity

Recall: We want to find equivalence function class that upper bounds
different t(n).

But we might be given an upper bound g(n) that isn’t quite in the form
of the equivalence classes. How to get the equivalence classes?

Adhere to the following guidelines:
• Do not include constants (e.g., omit ’-6’ in 0.01n − 6 to become

0.01n).
• Omit all the lower order terms (e.g., n3 + n2 + n, we simplify to n3).
• Omit the coefficient of the highest-order term (e.g., 0.01n

becomes n).
Returning to previous example, we can write the two upper bounds
O(0.01n − 6) and O(n) as O(n).

(RMIT University) Algorithmic Analysis Lecture 2 33 / 74

Example

Let

g(n) = 2n4 + 43n3 − n + 50

be an upper bound for the running time t(n) of an algorithm.

Using the previous guidelines, what equivalence class should
you use to describe the order of growth of the algorithm?

(RMIT University) Algorithmic Analysis Lecture 2 34 / 74

Asymptotic Complexity, Lower Bound (Ω(n))

Lower Bound Definition: Given a function t(n),
• Informally: t(n) ∈ Ω(g(n)) means g(n) is a function that, as n

increases, is a lower bound of t(n)
• Formally: t(n) ∈ Ω(g(n)), if g(n) is a function and c × g(n) is a

lower bound on t(n) for some c > 0 and for “large” n.

(RMIT University) Algorithmic Analysis Lecture 2 35 / 74

Asymptotic Complexity, Exact Bounds (Θ(n))

Exact Bound Definition: Given a function t(n),
• Informally: t(n) ∈ Θ(g(n)) means g(n) is a function that, as n

increases, is both a upper and lower bound of t(n)
• Formally: t(n) ∈ Θ(g(n)), if g(n) is a function and c1 × g(n) is an

upper bound on t(n) and c2 × g(n) is an lower bound on t(n), for
some c1 > 0 and c2 > 0 and for “large” n

(RMIT University) Algorithmic Analysis Lecture 2 36 / 74

Examples

t(n) O(n) O(n2) O(n3) Ω(n) Ω(n2) Ω(n3) Θ
log2 n T T T F F F Θ(log2 n)
10n + 5 T T T T F F Θ(n)
n(n − 1)/2 F T T T T F Θ(n2)
(n + 1)3 F F T T T T Θ(n3)
2n F F F T T T Θ(2n)

For example, 10n + 5 is in O(n).

(RMIT University) Algorithmic Analysis Lecture 2 37 / 74

Terminology Clarification

• O(n) is not the same thing as “Worst Case Efficiency”.
• Ω(n) is not the same thing as “ Efficiency”.
• Θ(n) is not the same thing as “Average Case Efficiency”.

It is perfectly reasonable to want the Ω(n) and O(n) worst case
efficiency bounds for a class of algorithms.

Why all the bounds?
• Generally O(n) is most commonly used , but exact bounds tell us

the bounds are tight and the algorithm doesn’t have anything
outside what we expect.
• Lower bounds are useful to describe the (theoretical) limits of

whole classes of algorithms, and also sometimes useful to state
how fast can the best case reach.

(RMIT University) Algorithmic Analysis Lecture 2 38 / 74

Terminology Clarification

• O(n) is not the same thing as “Worst Case Efficiency”.
• Ω(n) is not the same thing as “ Efficiency”.
• Θ(n) is not the same thing as “Average Case Efficiency”.

It is perfectly reasonable to want the Ω(n) and O(n) worst case
efficiency bounds for a class of algorithms.

Why all the bounds?
• Generally O(n) is most commonly used , but exact bounds tell us

the bounds are tight and the algorithm doesn’t have anything
outside what we expect.
• Lower bounds are useful to describe the (theoretical) limits of

whole classes of algorithms, and also sometimes useful to state
how fast can the best case reach.

(RMIT University) Algorithmic Analysis Lecture 2 38 / 74

Overview

1 Overview

2 Fundamentals

3 Asymptotic Complexity

4 Analysing Non-recursive Algorithms

5 Analysing Recursive Algorithms

6 Empirical Analysis

7 Rule of thumb Estimation of Complexity

8 Summary
(RMIT University) Algorithmic Analysis Lecture 2 39 / 74

Time Efficiency of Algorithms

Typically, we are given the pseudo code of an algorithm, not a nice t(n)
function.

Question
So how do we determine bounds on the order of growth of an
algorithm?

• Next two parts, we focus on answering this question.

• We first study how to do this for non-recursive algorithms, then
recursive ones.
• Keep in mind: Generally, we first need to estimate the running

time t(n), then determine a bound and order of growth.

(RMIT University) Algorithmic Analysis Lecture 2 40 / 74

Time Efficiency of Algorithms

Typically, we are given the pseudo code of an algorithm, not a nice t(n)
function.

Question
So how do we determine bounds on the order of growth of an
algorithm?

• Next two parts, we focus on answering this question.
• We first study how to do this for non-recursive algorithms, then

recursive ones.

• Keep in mind: Generally, we first need to estimate the running
time t(n), then determine a bound and order of growth.

(RMIT University) Algorithmic Analysis Lecture 2 40 / 74

Time Efficiency of Algorithms

Typically, we are given the pseudo code of an algorithm, not a nice t(n)
function.

Question
So how do we determine bounds on the order of growth of an
algorithm?

• Next two parts, we focus on answering this question.
• We first study how to do this for non-recursive algorithms, then

recursive ones.
• Keep in mind: Generally, we first need to estimate the running

time t(n), then determine a bound and order of growth.

(RMIT University) Algorithmic Analysis Lecture 2 40 / 74

Time Efficiency of Non-Recursive Algorithms

Question
So how do we determine bounds on the order of growth of an
algorithm?

Recall t(n) = copC(n).

1 Determine what is used to measure the input size.
2 Identify the algorithm’s basic operation
3 Determine the number of basic operation executions in terms of

the input size? (i.e., How to determine C(n)?)
• Setup a summation for C(n) reflecting the algorithm’s loop

structure.
• Simplify the summation by using standard formulas in Appendix A

of textbook.

4 Determine a equivalence class g(n) that bounds t(n). Recall we
generally want the tightest bound possible.

(RMIT University) Algorithmic Analysis Lecture 2 41 / 74

Time Efficiency of Non-Recursive Algorithms

Question
So how do we determine bounds on the order of growth of an
algorithm?

Recall t(n) = copC(n).
1 Determine what is used to measure the input size.
2 Identify the algorithm’s basic operation

3 Determine the number of basic operation executions in terms of
the input size? (i.e., How to determine C(n)?)
• Setup a summation for C(n) reflecting the algorithm’s loop

structure.
• Simplify the summation by using standard formulas in Appendix A

of textbook.

4 Determine a equivalence class g(n) that bounds t(n). Recall we
generally want the tightest bound possible.

(RMIT University) Algorithmic Analysis Lecture 2 41 / 74

Time Efficiency of Non-Recursive Algorithms

Question
So how do we determine bounds on the order of growth of an
algorithm?

Recall t(n) = copC(n).
1 Determine what is used to measure the input size.
2 Identify the algorithm’s basic operation
3 Determine the number of basic operation executions in terms of

the input size? (i.e., How to determine C(n)?)
• Setup a summation for C(n) reflecting the algorithm’s loop

structure.
• Simplify the summation by using standard formulas in Appendix A

of textbook.

4 Determine a equivalence class g(n) that bounds t(n). Recall we
generally want the tightest bound possible.

(RMIT University) Algorithmic Analysis Lecture 2 41 / 74

Time Efficiency of Non-Recursive Algorithms

Question
So how do we determine bounds on the order of growth of an
algorithm?

Recall t(n) = copC(n).
1 Determine what is used to measure the input size.
2 Identify the algorithm’s basic operation
3 Determine the number of basic operation executions in terms of

the input size? (i.e., How to determine C(n)?)
• Setup a summation for C(n) reflecting the algorithm’s loop

structure.
• Simplify the summation by using standard formulas in Appendix A

of textbook.

4 Determine a equivalence class g(n) that bounds t(n). Recall we
generally want the tightest bound possible.

(RMIT University) Algorithmic Analysis Lecture 2 41 / 74

Non Recusive Example: an

// INPUT : a, n
// OUTPUT : s = an

1: set s = 1
2: for i = 1 to n do
3: s = s ∗ a
4: end for
5: return

Input size: n
Basic operation: multiplication
C(n): ? 1 + 1 + 1 + . . . + 1︸︷︷︸

=
∑n

i=1 1

(RMIT University) Algorithmic Analysis Lecture 2 42 / 74

Non Recusive Example: an

// INPUT : a, n
// OUTPUT : s = an

1: set s = 1
2: for i = 1 to n do
3: s = s ∗ a
4: end for
5: return

Input size: n
Basic operation: multiplication
C(n): ?

1 + 1 + 1 + . . . + 1︸︷︷︸
n

=
∑n

i=1 1

(RMIT University) Algorithmic Analysis Lecture 2 42 / 74

Non Recusive Example: an

// INPUT : a, n
// OUTPUT : s = an

1: set s = 1
2: for i = 1 to n do
3: s = s ∗ a
4: end for
5: return

Input size: n
Basic operation: multiplication
C(n): ? 1 + 1 + 1 + . . . + 1︸︷︷︸

=
∑n

i=1 1

(RMIT University) Algorithmic Analysis Lecture 2 42 / 74

Non Recusive Example: an

// INPUT : a, n
// OUTPUT : s = an

1: set s = 1
2: for i = 1 to n do
3: s = s ∗ a
4: end for
5: return

Input size: n
Basic operation: multiplication
C(n): ? 1 + 1 + 1 + . . . + 1︸︷︷︸

=
∑n

i=1 1

(RMIT University) Algorithmic Analysis Lecture 2 42 / 74

Non-Recursive Examples (continued): Adding two matrices

Given two (square) matrices A and B, both of dimensions n by n, the
following algorithm computes C = A + B.

for ( i n t i = 0 ; i <= n−1; i ++) { for ( i n t j = 0 ; j <= n−1; j ++) { C[ i , j ] = A [ i , j ] + B [ i , j ] ; } } Input size: ? n Basic operation: ? addition C(n): ? n−1∑ i=0 n−1∑ j=0 1 (RMIT University) Algorithmic Analysis Lecture 2 43 / 74 Non-Recursive Examples (continued): Adding two matrices Given two (square) matrices A and B, both of dimensions n by n, the following algorithm computes C = A + B. for ( i n t i = 0 ; i <= n−1; i ++) { for ( i n t j = 0 ; j <= n−1; j ++) { C[ i , j ] = A [ i , j ] + B [ i , j ] ; } } Input size: ? n Basic operation: ? addition C(n): ? n−1∑ i=0 n−1∑ j=0 1 (RMIT University) Algorithmic Analysis Lecture 2 43 / 74 Non-Recursive Examples (continued): Adding two matrices Given two (square) matrices A and B, both of dimensions n by n, the following algorithm computes C = A + B. for ( i n t i = 0 ; i <= n−1; i ++) { for ( i n t j = 0 ; j <= n−1; j ++) { C[ i , j ] = A [ i , j ] + B [ i , j ] ; } } Input size: ? n Basic operation: ? addition C(n): ? n−1∑ i=0 n−1∑ j=0 1 (RMIT University) Algorithmic Analysis Lecture 2 43 / 74 Non-Recursive Examples (continued): Adding two matrices Given two (square) matrices A and B, both of dimensions n by n, the following algorithm computes C = A + B. for ( i n t i = 0 ; i <= n−1; i ++) { for ( i n t j = 0 ; j <= n−1; j ++) { C[ i , j ] = A [ i , j ] + B [ i , j ] ; } } Input size: ? n Basic operation: ? addition C(n): ? n−1∑ i=0 n−1∑ j=0 1 (RMIT University) Algorithmic Analysis Lecture 2 43 / 74 Non-Recursive Examples (continued): Adding two matrices Given two (square) matrices A and B, both of dimensions n by n, the following algorithm computes C = A + B. for ( i n t i = 0 ; i <= n−1; i ++) { for ( i n t j = 0 ; j <= n−1; j ++) { C[ i , j ] = A [ i , j ] + B [ i , j ] ; } } Input size: ? n Basic operation: ? addition C(n): ? n−1∑ i=0 n−1∑ j=0 1 (RMIT University) Algorithmic Analysis Lecture 2 43 / 74 Time Efficiency of Non-Recursive Algorithms Question So how do we determine bounds on the order of growth of an algorithm? Recall t(n) = copC(n). 1 Determine what is used to measure the input size. 2 Identify the algorithm’s basic operation. 3 Determine the number of basic operation executions in terms of the input size? (i.e., How to determine C(n)?) • Setup a summation for C(n) reflecting the algorithm’s loop structure. • Simplify the summation by using standard formulas in Appendix A of textbook. 4 Determine a function family g(n) that bounds t(n). Recall we generally want the tightest bound possible. (RMIT University) Algorithmic Analysis Lecture 2 44 / 74 Useful series (from Appendix A) • R1 (Sum): ∑n i=l 1 = n − l + 1. • R2 (Geometric): ∑n i=1 i = n(n+1) 2 . • R3 (Distributive): ∑n i=1 c ∗ ai = c ∑n i=1 ai . • R4 (Associative): ∑n i=1(ai ± bi) = ∑n i=1 ai ± ∑n i=1 bi . (RMIT University) Algorithmic Analysis Lecture 2 45 / 74 Non Recusive Example an: Simplification // INPUT : a, n // OUTPUT : s = an 1: set s = 1 2: for i = 1 : n do 3: s = s ∗ a 4: end for 5: return C(n) = ∑n i=1 1 (RMIT University) Algorithmic Analysis Lecture 2 46 / 74 Non Recusive Example an: Simplification C(n) = n∑ i=1 1 (1) = n − 1 + 1 (Use R1) (2) = n (3) (RMIT University) Algorithmic Analysis Lecture 2 47 / 74 Non Recusive Example an: Simplification C(n) = n∑ i=1 1 (1) = n − 1 + 1 (Use R1) (2) = n (3) (RMIT University) Algorithmic Analysis Lecture 2 47 / 74 Non Recusive Example an: Simplification C(n) = n∑ i=1 1 (1) = n − 1 + 1 (Use R1) (2) = n (3) (RMIT University) Algorithmic Analysis Lecture 2 47 / 74 Non-Recursive Example Adding two matrices: Simplication Given two (square) matrices A and B, both of dimensions n by n, the following algorithm computes C = A + B. Example: for ( i n t i = 0 ; i <= n−1; i ++) { for ( i n t j = 0 ; j <= n−1; j ++) { C[ i , j ] = A [ i , j ] + B [ i , j ] ; } } C(n) = ∑n−1 i=0 ∑n−1 j=0 1 (RMIT University) Algorithmic Analysis Lecture 2 48 / 74 Non-Recursive Example Adding two matrices: Simplication C(n) = n−1∑ i=0 n−1∑ j=0 1 (1) = n−1∑ i=0 (n − 1 + 1) (Use R1 on inner summation) (2) = n−1∑ i=0 (n) (Simplify) (3) = n n−1∑ i=0 1 (Use R3 to take n out of summation) (4) = n ∗ (n − 1 + 1) (Use R1 on remaining summation) (5) = n ∗ n (Simplify) (6) (RMIT University) Algorithmic Analysis Lecture 2 49 / 74 Non-Recursive Example Adding two matrices: Simplication C(n) = n−1∑ i=0 n−1∑ j=0 1 (1) = n−1∑ i=0 (n − 1 + 1) (Use R1 on inner summation) (2) = n−1∑ i=0 (n) (Simplify) (3) = n n−1∑ i=0 1 (Use R3 to take n out of summation) (4) = n ∗ (n − 1 + 1) (Use R1 on remaining summation) (5) = n ∗ n (Simplify) (6) (RMIT University) Algorithmic Analysis Lecture 2 49 / 74 Non-Recursive Example Adding two matrices: Simplication C(n) = n−1∑ i=0 n−1∑ j=0 1 (1) = n−1∑ i=0 (n − 1 + 1) (Use R1 on inner summation) (2) = n−1∑ i=0 (n) (Simplify) (3) = n n−1∑ i=0 1 (Use R3 to take n out of summation) (4) = n ∗ (n − 1 + 1) (Use R1 on remaining summation) (5) = n ∗ n (Simplify) (6) (RMIT University) Algorithmic Analysis Lecture 2 49 / 74 Non-Recursive Example Adding two matrices: Simplication C(n) = n−1∑ i=0 n−1∑ j=0 1 (1) = n−1∑ i=0 (n − 1 + 1) (Use R1 on inner summation) (2) = n−1∑ i=0 (n) (Simplify) (3) = n n−1∑ i=0 1 (Use R3 to take n out of summation) (4) = n ∗ (n − 1 + 1) (Use R1 on remaining summation) (5) = n ∗ n (Simplify) (6) (RMIT University) Algorithmic Analysis Lecture 2 49 / 74 Non-Recursive Example Adding two matrices: Simplication C(n) = n−1∑ i=0 n−1∑ j=0 1 (1) = n−1∑ i=0 (n − 1 + 1) (Use R1 on inner summation) (2) = n−1∑ i=0 (n) (Simplify) (3) = n n−1∑ i=0 1 (Use R3 to take n out of summation) (4) = n ∗ (n − 1 + 1) (Use R1 on remaining summation) (5) = n ∗ n (Simplify) (6) (RMIT University) Algorithmic Analysis Lecture 2 49 / 74 Non-Recursive Example Adding two matrices: Simplication C(n) = n−1∑ i=0 n−1∑ j=0 1 (1) = n−1∑ i=0 (n − 1 + 1) (Use R1 on inner summation) (2) = n−1∑ i=0 (n) (Simplify) (3) = n n−1∑ i=0 1 (Use R3 to take n out of summation) (4) = n ∗ (n − 1 + 1) (Use R1 on remaining summation) (5) = n ∗ n (Simplify) (6) (RMIT University) Algorithmic Analysis Lecture 2 49 / 74 Overview 1 Overview 2 Fundamentals 3 Asymptotic Complexity 4 Analysing Non-recursive Algorithms 5 Analysing Recursive Algorithms 6 Empirical Analysis 7 Rule of thumb Estimation of Complexity 8 Summary (RMIT University) Algorithmic Analysis Lecture 2 50 / 74 Recursion • Recursion is fundamental tool in computer science. • A recursive program (or function) is one that calls itself. • It must have a termination condition defined. • Many interesting algorithms are simply expressed with a recursive approach. (RMIT University) Algorithmic Analysis Lecture 2 51 / 74 Recursion • Recursion is fundamental tool in computer science. • A recursive program (or function) is one that calls itself. • It must have a termination condition defined. • Many interesting algorithms are simply expressed with a recursive approach. (RMIT University) Algorithmic Analysis Lecture 2 51 / 74 Recursive Algorithm Example: Factorial Factorial: F(n) = n ∗ (n − 1) ∗ (n − 2) ∗ (n − 3) ∗ . . . ∗ 3 ∗ 2 ∗ 1 ALGORITHM F(n) 1: if n = 1 then 2: return 1 3: else 4: return F(n − 1) ∗ n 5: end if (RMIT University) Algorithmic Analysis Lecture 2 52 / 74 Time Efficiency of Recursive Algorithms 1 Determine what is used to measure the input size. 2 Identify the algorithm’s basic operation 3 Setup a recurrence relation for C(n), including termination condition(s). 4 Simplify the recurrence relation using methods in Appendix B of textbook. (Backward substitution) 5 Determine an equivalence class g(n) that bounds t(n) = copC(n). Recall we generally want the tightest bound possible. (RMIT University) Algorithmic Analysis Lecture 2 53 / 74 Time Efficiency of Recursive Algorithms 1 Determine what is used to measure the input size. 2 Identify the algorithm’s basic operation 3 Setup a recurrence relation for C(n), including termination condition(s). 4 Simplify the recurrence relation using methods in Appendix B of textbook. (Backward substitution) 5 Determine an equivalence class g(n) that bounds t(n) = copC(n). Recall we generally want the tightest bound possible. (RMIT University) Algorithmic Analysis Lecture 2 53 / 74 Time Efficiency of Recursive Algorithms 1 Determine what is used to measure the input size. 2 Identify the algorithm’s basic operation 3 Setup a recurrence relation for C(n), including termination condition(s). 4 Simplify the recurrence relation using methods in Appendix B of textbook. (Backward substitution) 5 Determine an equivalence class g(n) that bounds t(n) = copC(n). Recall we generally want the tightest bound possible. (RMIT University) Algorithmic Analysis Lecture 2 53 / 74 Recurrence Relations A recurrence relation represents a sequence of terms, that results from a recursion on one or more of the previous terms. The recurrence relation include the termination condition. For example, the sequence for a factorial of n, F (n) = n ∗ (n− 1) ∗ (n− 2) ∗ (n− 3) ∗ . . . ∗ 3 ∗ 2 ∗ 1, can be represented as the recurrence relation: F (n) = F (n − 1) ∗ n, F (1) = 1 (RMIT University) Algorithmic Analysis Lecture 2 54 / 74 Recurrence Relations A recurrence relation represents a sequence of terms, that results from a recursion on one or more of the previous terms. The recurrence relation include the termination condition. For example, the sequence for a factorial of n, F (n) = n ∗ (n− 1) ∗ (n− 2) ∗ (n− 3) ∗ . . . ∗ 3 ∗ 2 ∗ 1, can be represented as the recurrence relation: F (n) = F (n − 1) ∗ n, F (1) = 1 (RMIT University) Algorithmic Analysis Lecture 2 54 / 74 Recurrence Relations A recurrence relation represents a sequence of terms, that results from a recursion on one or more of the previous terms. The recurrence relation include the termination condition. For example, the sequence for a factorial of n, F (n) = n ∗ (n− 1) ∗ (n− 2) ∗ (n− 3) ∗ . . . ∗ 3 ∗ 2 ∗ 1, can be represented as the recurrence relation: F (n) = F (n − 1) ∗ n, F (1) = 1 (RMIT University) Algorithmic Analysis Lecture 2 54 / 74 Time Efficiency of Recursive Algorithms 1 Determine what is used to measure the input size. 2 Identify the algorithm’s basic operation. 3 Setup a recurrence relation for C(n), including termination condition(s). 4 Simplify the recurrence relation using methods in Appendix B of textbook. (Backward substitution) 5 Determine a function family g(n) that bounds t(n) = copC(n). Recall we generally want the tightest bound possible. (RMIT University) Algorithmic Analysis Lecture 2 55 / 74 Recursive Algorithm Example: Factorial ALGORITHM F(n) 1: if n = 1 then 2: return 1 3: else 4: return F(n − 1) ∗ n 5: end if Basic operation: ? multiplication Input size: ? n, Recurrence relation and conditions: The number of multiplications is C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0.
• “+1” is the number of multiplication operations at each recursive

step.
• When n = 1, we have our termination/base case, where we stop

the recursion. When we reach this base case, the number of
multiplcations is 0, hence C(1) = 0.

(RMIT University) Algorithmic Analysis Lecture 2 56 / 74

Recursive Algorithm Example: Factorial

ALGORITHM F(n)
1: if n = 1 then
2: return 1
3: else
4: return F(n − 1) ∗ n
5: end if

Basic operation: ?

multiplication Input size: ? n,

Recurrence relation and conditions: The number of multiplications
is C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0.
• “+1” is the number of multiplication operations at each recursive

step.
• When n = 1, we have our termination/base case, where we stop

the recursion. When we reach this base case, the number of
multiplcations is 0, hence C(1) = 0.

(RMIT University) Algorithmic Analysis Lecture 2 56 / 74

Recursive Algorithm Example: Factorial

ALGORITHM F(n)
1: if n = 1 then
2: return 1
3: else
4: return F(n − 1) ∗ n
5: end if

Basic operation: ? multiplication Input size: ?

Recurrence relation and conditions: The number of multiplications
is C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0.
• “+1” is the number of multiplication operations at each recursive

step.
• When n = 1, we have our termination/base case, where we stop

the recursion. When we reach this base case, the number of
multiplcations is 0, hence C(1) = 0.

(RMIT University) Algorithmic Analysis Lecture 2 56 / 74

Recursive Algorithm Example: Factorial

ALGORITHM F(n)
1: if n = 1 then
2: return 1
3: else
4: return F(n − 1) ∗ n
5: end if

Basic operation: ? multiplication Input size: ? n,

Recurrence relation and conditions: The number of multiplications
is C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0.
• “+1” is the number of multiplication operations at each recursive

step.
• When n = 1, we have our termination/base case, where we stop

the recursion. When we reach this base case, the number of
multiplcations is 0, hence C(1) = 0.

(RMIT University) Algorithmic Analysis Lecture 2 56 / 74

Recursive Algorithm Example: Factorial

ALGORITHM F(n)
1: if n = 1 then
2: return 1
3: else
4: return F(n − 1) ∗ n
5: end if

Basic operation: ? multiplication Input size: ? n,

Recurrence relation and conditions: The number of multiplications
is C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0.

• “+1” is the number of multiplication operations at each recursive
step.

• When n = 1, we have our termination/base case, where we stop
the recursion. When we reach this base case, the number of
multiplcations is 0, hence C(1) = 0.

(RMIT University) Algorithmic Analysis Lecture 2 56 / 74

Recursive Algorithm Example: Factorial

ALGORITHM F(n)
1: if n = 1 then
2: return 1
3: else
4: return F(n − 1) ∗ n
5: end if

Basic operation: ? multiplication Input size: ? n,

Recurrence relation and conditions: The number of multiplications
is C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0.
• “+1” is the number of multiplication operations at each recursive

step.

• When n = 1, we have our termination/base case, where we stop
the recursion. When we reach this base case, the number of
multiplcations is 0, hence C(1) = 0.

(RMIT University) Algorithmic Analysis Lecture 2 56 / 74

Recursive Algorithm Example: Factorial

ALGORITHM F(n)
1: if n = 1 then
2: return 1
3: else
4: return F(n − 1) ∗ n
5: end if

Basic operation: ? multiplication Input size: ? n,

Recurrence relation and conditions: The number of multiplications
is C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0.
• “+1” is the number of multiplication operations at each recursive

step.
• When n = 1, we have our termination/base case, where we stop

the recursion. When we reach this base case, the number of
multiplcations is 0, hence C(1) = 0.

(RMIT University) Algorithmic Analysis Lecture 2 56 / 74

Time Efficiency of Recursive Algorithms

1 Determine what is used to measure the input size.
2 Identify the algorithm’s basic operation.
3 Setup a recurrence relation for C(n), including termination

condition(s).
4 Simplify the recurrence relation using methods in Appendix B of

textbook. (Backward substitution)
5 Determine a function family g(n) that bounds t(n) = copC(n).

Recall we generally want the tightest bound possible.

(RMIT University) Algorithmic Analysis Lecture 2 57 / 74

Backward Substitution: Factorial Example

Recurrence: C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0

Aim of simplification and backward substitution: Convert
C(n) = C(n − 1) + 1 to C(n) = function(n), e.g., C(n) = n + 1.

1 Start with the recurrence relation: C(n) = C(n − 1) + . . .
2 Substitute C(n − 1) with its RHS (C(n − 1) = C(n − 2) + . . .) in

original equation C(n) = C(n − 2) + . . .
3 Substitute C(n − 2) with its RHS (C(n − 2) = C(n − 3) + . . .) in

original equation C(n) = C(n − 3) + . . .
4 Spot the pattern of C(n) and introduce a variable to express this

pattern.
5 Determine when the value of this variable that relates

C(n) = C(1) + . . .
6 Substitute the value of C(1) and get C(n) in terms of some

expression of n.

(RMIT University) Algorithmic Analysis Lecture 2 58 / 74

Backward Substitution: Factorial Example

Recurrence: C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0

Aim of simplification and backward substitution: Convert
C(n) = C(n − 1) + 1 to C(n) = function(n), e.g., C(n) = n + 1.

1 Start with the recurrence relation: C(n) = C(n − 1) + . . .

2 Substitute C(n − 1) with its RHS (C(n − 1) = C(n − 2) + . . .) in
original equation C(n) = C(n − 2) + . . .

3 Substitute C(n − 2) with its RHS (C(n − 2) = C(n − 3) + . . .) in
original equation C(n) = C(n − 3) + . . .

4 Spot the pattern of C(n) and introduce a variable to express this
pattern.

5 Determine when the value of this variable that relates
C(n) = C(1) + . . .

6 Substitute the value of C(1) and get C(n) in terms of some
expression of n.

(RMIT University) Algorithmic Analysis Lecture 2 58 / 74

Backward Substitution: Factorial Example

Recurrence: C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0

Aim of simplification and backward substitution: Convert
C(n) = C(n − 1) + 1 to C(n) = function(n), e.g., C(n) = n + 1.

1 Start with the recurrence relation: C(n) = C(n − 1) + . . .
2 Substitute C(n − 1) with its RHS (C(n − 1) = C(n − 2) + . . .) in

original equation C(n) = C(n − 2) + . . .

3 Substitute C(n − 2) with its RHS (C(n − 2) = C(n − 3) + . . .) in
original equation C(n) = C(n − 3) + . . .

4 Spot the pattern of C(n) and introduce a variable to express this
pattern.

5 Determine when the value of this variable that relates
C(n) = C(1) + . . .

6 Substitute the value of C(1) and get C(n) in terms of some
expression of n.

(RMIT University) Algorithmic Analysis Lecture 2 58 / 74

Backward Substitution: Factorial Example

Recurrence: C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0

Aim of simplification and backward substitution: Convert
C(n) = C(n − 1) + 1 to C(n) = function(n), e.g., C(n) = n + 1.

1 Start with the recurrence relation: C(n) = C(n − 1) + . . .
2 Substitute C(n − 1) with its RHS (C(n − 1) = C(n − 2) + . . .) in

original equation C(n) = C(n − 2) + . . .
3 Substitute C(n − 2) with its RHS (C(n − 2) = C(n − 3) + . . .) in

original equation C(n) = C(n − 3) + . . .

4 Spot the pattern of C(n) and introduce a variable to express this
pattern.

5 Determine when the value of this variable that relates
C(n) = C(1) + . . .

6 Substitute the value of C(1) and get C(n) in terms of some
expression of n.

(RMIT University) Algorithmic Analysis Lecture 2 58 / 74

Backward Substitution: Factorial Example

Recurrence: C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0

Aim of simplification and backward substitution: Convert
C(n) = C(n − 1) + 1 to C(n) = function(n), e.g., C(n) = n + 1.

1 Start with the recurrence relation: C(n) = C(n − 1) + . . .
2 Substitute C(n − 1) with its RHS (C(n − 1) = C(n − 2) + . . .) in

original equation C(n) = C(n − 2) + . . .
3 Substitute C(n − 2) with its RHS (C(n − 2) = C(n − 3) + . . .) in

original equation C(n) = C(n − 3) + . . .
4 Spot the pattern of C(n) and introduce a variable to express this

pattern.

5 Determine when the value of this variable that relates
C(n) = C(1) + . . .

6 Substitute the value of C(1) and get C(n) in terms of some
expression of n.

(RMIT University) Algorithmic Analysis Lecture 2 58 / 74

Backward Substitution: Factorial Example

Recurrence: C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0

Aim of simplification and backward substitution: Convert
C(n) = C(n − 1) + 1 to C(n) = function(n), e.g., C(n) = n + 1.

1 Start with the recurrence relation: C(n) = C(n − 1) + . . .
2 Substitute C(n − 1) with its RHS (C(n − 1) = C(n − 2) + . . .) in

original equation C(n) = C(n − 2) + . . .
3 Substitute C(n − 2) with its RHS (C(n − 2) = C(n − 3) + . . .) in

original equation C(n) = C(n − 3) + . . .
4 Spot the pattern of C(n) and introduce a variable to express this

pattern.
5 Determine when the value of this variable that relates

C(n) = C(1) + . . .

6 Substitute the value of C(1) and get C(n) in terms of some
expression of n.

(RMIT University) Algorithmic Analysis Lecture 2 58 / 74

Backward Substitution: Factorial Example

Recurrence: C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0

Aim of simplification and backward substitution: Convert
C(n) = C(n − 1) + 1 to C(n) = function(n), e.g., C(n) = n + 1.

1 Start with the recurrence relation: C(n) = C(n − 1) + . . .
2 Substitute C(n − 1) with its RHS (C(n − 1) = C(n − 2) + . . .) in

original equation C(n) = C(n − 2) + . . .
3 Substitute C(n − 2) with its RHS (C(n − 2) = C(n − 3) + . . .) in

original equation C(n) = C(n − 3) + . . .
4 Spot the pattern of C(n) and introduce a variable to express this

pattern.
5 Determine when the value of this variable that relates

C(n) = C(1) + . . .
6 Substitute the value of C(1) and get C(n) in terms of some

expression of n.

(RMIT University) Algorithmic Analysis Lecture 2 58 / 74

Backward Substitution: Factorial Example

Recurrence: C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0

1. C(n) = C(n − 1) + 1
2. Substitute C(n − 1) = C(n − 2) + 1 into original equation
3. C(n) = [C(n − 2) + 1] + 1 = C(n − 2) + 2
4. Substitute C(n − 2) = C(n − 3) + 1 into original equation
5. C(n) = [C(n − 3) + 1] + 2 = C(n − 3) + 3
6. We see the pattern C(n) = C(n − i) + i emerge, where 1 ≤ i ≤ n.
7. Now, we know C(1) and want to determine when C(n − i) = C(1),

or when n − i = 1. This value is i = n − 1.
C(n) = C(n− (n − 1)) + n − 1 = C(1) + n− 1 = 0 + n− 1 = n− 1.

Hence t(n) = cop · (n − 1) ∈ O(n).

(RMIT University) Algorithmic Analysis Lecture 2 59 / 74

Backward Substitution: Factorial Example

Recurrence: C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0

1. C(n) = C(n − 1) + 1

2. Substitute C(n − 1) = C(n − 2) + 1 into original equation
3. C(n) = [C(n − 2) + 1] + 1 = C(n − 2) + 2
4. Substitute C(n − 2) = C(n − 3) + 1 into original equation
5. C(n) = [C(n − 3) + 1] + 2 = C(n − 3) + 3
6. We see the pattern C(n) = C(n − i) + i emerge, where 1 ≤ i ≤ n.
7. Now, we know C(1) and want to determine when C(n − i) = C(1),

or when n − i = 1. This value is i = n − 1.
C(n) = C(n− (n − 1)) + n − 1 = C(1) + n− 1 = 0 + n− 1 = n− 1.

Hence t(n) = cop · (n − 1) ∈ O(n).

(RMIT University) Algorithmic Analysis Lecture 2 59 / 74

Backward Substitution: Factorial Example

Recurrence: C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0

1. C(n) = C(n − 1) + 1
2. Substitute C(n − 1) = C(n − 2) + 1 into original equation

3. C(n) = [C(n − 2) + 1] + 1 = C(n − 2) + 2
4. Substitute C(n − 2) = C(n − 3) + 1 into original equation
5. C(n) = [C(n − 3) + 1] + 2 = C(n − 3) + 3
6. We see the pattern C(n) = C(n − i) + i emerge, where 1 ≤ i ≤ n.
7. Now, we know C(1) and want to determine when C(n − i) = C(1),

or when n − i = 1. This value is i = n − 1.
C(n) = C(n− (n − 1)) + n − 1 = C(1) + n− 1 = 0 + n− 1 = n− 1.

Hence t(n) = cop · (n − 1) ∈ O(n).

(RMIT University) Algorithmic Analysis Lecture 2 59 / 74

Backward Substitution: Factorial Example

Recurrence: C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0

1. C(n) = C(n − 1) + 1
2. Substitute C(n − 1) = C(n − 2) + 1 into original equation
3. C(n) = [C(n − 2) + 1] + 1 = C(n − 2) + 2

4. Substitute C(n − 2) = C(n − 3) + 1 into original equation
5. C(n) = [C(n − 3) + 1] + 2 = C(n − 3) + 3
6. We see the pattern C(n) = C(n − i) + i emerge, where 1 ≤ i ≤ n.
7. Now, we know C(1) and want to determine when C(n − i) = C(1),

or when n − i = 1. This value is i = n − 1.
C(n) = C(n− (n − 1)) + n − 1 = C(1) + n− 1 = 0 + n− 1 = n− 1.

Hence t(n) = cop · (n − 1) ∈ O(n).

(RMIT University) Algorithmic Analysis Lecture 2 59 / 74

Backward Substitution: Factorial Example

Recurrence: C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0

1. C(n) = C(n − 1) + 1
2. Substitute C(n − 1) = C(n − 2) + 1 into original equation
3. C(n) = [C(n − 2) + 1] + 1 = C(n − 2) + 2
4. Substitute C(n − 2) = C(n − 3) + 1 into original equation

5. C(n) = [C(n − 3) + 1] + 2 = C(n − 3) + 3
6. We see the pattern C(n) = C(n − i) + i emerge, where 1 ≤ i ≤ n.
7. Now, we know C(1) and want to determine when C(n − i) = C(1),

or when n − i = 1. This value is i = n − 1.
C(n) = C(n− (n − 1)) + n − 1 = C(1) + n− 1 = 0 + n− 1 = n− 1.

Hence t(n) = cop · (n − 1) ∈ O(n).

(RMIT University) Algorithmic Analysis Lecture 2 59 / 74

Backward Substitution: Factorial Example

Recurrence: C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0

6. We see the pattern C(n) = C(n − i) + i emerge, where 1 ≤ i ≤ n.
7. Now, we know C(1) and want to determine when C(n − i) = C(1),

or when n − i = 1. This value is i = n − 1.
C(n) = C(n− (n − 1)) + n − 1 = C(1) + n− 1 = 0 + n− 1 = n− 1.

Hence t(n) = cop · (n − 1) ∈ O(n).

(RMIT University) Algorithmic Analysis Lecture 2 59 / 74

Backward Substitution: Factorial Example

Recurrence: C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0

7. Now, we know C(1) and want to determine when C(n − i) = C(1),
or when n − i = 1. This value is i = n − 1.
C(n) = C(n− (n − 1)) + n − 1 = C(1) + n− 1 = 0 + n− 1 = n− 1.

Hence t(n) = cop · (n − 1) ∈ O(n).

(RMIT University) Algorithmic Analysis Lecture 2 59 / 74

Backward Substitution: Factorial Example

Recurrence: C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0

or when n − i = 1. This value is i = n − 1.

C(n) = C(n− (n − 1)) + n − 1 = C(1) + n− 1 = 0 + n− 1 = n− 1.
Hence t(n) = cop · (n − 1) ∈ O(n).

(RMIT University) Algorithmic Analysis Lecture 2 59 / 74

Backward Substitution: Factorial Example

Recurrence: C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0

or when n − i = 1. This value is i = n − 1.
C(n) = C(n− (n − 1)) + n − 1 = C(1) + n− 1 = 0 + n− 1 = n− 1.

Hence t(n) = cop · (n − 1) ∈ O(n).

(RMIT University) Algorithmic Analysis Lecture 2 59 / 74

Backward Substitution: Factorial Example

Recurrence: C(n) = C(n − 1) + 1 for n > 1, and C(1) = 0

or when n − i = 1. This value is i = n − 1.
C(n) = C(n− (n − 1)) + n − 1 = C(1) + n− 1 = 0 + n− 1 = n− 1.

Hence t(n) = cop · (n − 1) ∈ O(n).

(RMIT University) Algorithmic Analysis Lecture 2 59 / 74

Summary of these parts

• (non-recursive algorithm) Discussed now to write down expression
for C(n) (number of basic operations executed in algorithm).
• Discussed how to simply this for non-recursive algorithm.
• (recursive algorithm) Discussed the idea of recurrence and how to

write C(n).
• Discussed how to simply via backward substitution.

(RMIT University) Algorithmic Analysis Lecture 2 60 / 74

Overview

1 Overview

2 Fundamentals

3 Asymptotic Complexity

4 Analysing Non-recursive Algorithms

5 Analysing Recursive Algorithms

6 Empirical Analysis

7 Rule of thumb Estimation of Complexity

8 Summary
(RMIT University) Algorithmic Analysis Lecture 2 61 / 74

Theory vs Practice

Formal Analysis (theoretical):
• Pro: No interference from implementation / hardware details.
• Con: Hides constant factors. Requires a different mindset.

Empirical Analysis (measure):
• Pro: Discovers the true impact of constant factors.
• Con: May be running on the “wrong” inputs.

“In theory, theory and practice are the same. In practice, they are not.”
–

(RMIT University) Algorithmic Analysis Lecture 2 62 / 74

Empirical Analysis

• The complexity of an algorithm gives an estimate of the running
time (we discussed this in detail).
• Measuring the actual time an implementation takes is also

important, especially when comparing two algorithms with the
same time complexity.
• When in doubt, measure!

(RMIT University) Algorithmic Analysis Lecture 2 63 / 74

Empirical Analysis of Algorithm Time Efficiency

When designing experiments:
1 Understand the experiment’s purpose.

2 Decide on the efficiency metric M to be measured and the
measurement unit (an operation’s count vs. a time unit).

3 Decide on characteristics of the input sample (its range, size, and
so on).

4 Prepare a program implementing the algorithm (or algorithms) for
the experimentation.

5 Generate a sample of inputs.
6 Run the algorithm (or algorithms) on the sample’s inputs and

record the data observed.
7 Analyse the data obtained.

(RMIT University) Algorithmic Analysis Lecture 2 64 / 74

Empirical Analysis of Algorithm Time Efficiency

When designing experiments:
1 Understand the experiment’s purpose.
2 Decide on the efficiency metric M to be measured and the

measurement unit (an operation’s count vs. a time unit).

3 Decide on characteristics of the input sample (its range, size, and
so on).

4 Prepare a program implementing the algorithm (or algorithms) for
the experimentation.

5 Generate a sample of inputs.
6 Run the algorithm (or algorithms) on the sample’s inputs and

record the data observed.
7 Analyse the data obtained.

(RMIT University) Algorithmic Analysis Lecture 2 64 / 74

Empirical Analysis of Algorithm Time Efficiency

When designing experiments:
1 Understand the experiment’s purpose.
2 Decide on the efficiency metric M to be measured and the

measurement unit (an operation’s count vs. a time unit).
3 Decide on characteristics of the input sample (its range, size, and

so on).

4 Prepare a program implementing the algorithm (or algorithms) for
the experimentation.

5 Generate a sample of inputs.
6 Run the algorithm (or algorithms) on the sample’s inputs and

record the data observed.
7 Analyse the data obtained.

(RMIT University) Algorithmic Analysis Lecture 2 64 / 74

Empirical Analysis of Algorithm Time Efficiency

When designing experiments:
1 Understand the experiment’s purpose.
2 Decide on the efficiency metric M to be measured and the

measurement unit (an operation’s count vs. a time unit).
3 Decide on characteristics of the input sample (its range, size, and

so on).
4 Prepare a program implementing the algorithm (or algorithms) for

the experimentation.

5 Generate a sample of inputs.
6 Run the algorithm (or algorithms) on the sample’s inputs and

record the data observed.
7 Analyse the data obtained.

(RMIT University) Algorithmic Analysis Lecture 2 64 / 74

Empirical Analysis of Algorithm Time Efficiency

When designing experiments:
1 Understand the experiment’s purpose.
2 Decide on the efficiency metric M to be measured and the

measurement unit (an operation’s count vs. a time unit).
3 Decide on characteristics of the input sample (its range, size, and

so on).
4 Prepare a program implementing the algorithm (or algorithms) for

the experimentation.
5 Generate a sample of inputs.

6 Run the algorithm (or algorithms) on the sample’s inputs and
record the data observed.

7 Analyse the data obtained.

(RMIT University) Algorithmic Analysis Lecture 2 64 / 74

Empirical Analysis of Algorithm Time Efficiency

When designing experiments:
1 Understand the experiment’s purpose.
2 Decide on the efficiency metric M to be measured and the

measurement unit (an operation’s count vs. a time unit).
3 Decide on characteristics of the input sample (its range, size, and

so on).
4 Prepare a program implementing the algorithm (or algorithms) for

the experimentation.
5 Generate a sample of inputs.
6 Run the algorithm (or algorithms) on the sample’s inputs and

record the data observed.

7 Analyse the data obtained.

(RMIT University) Algorithmic Analysis Lecture 2 64 / 74

Empirical Analysis of Algorithm Time Efficiency

When designing experiments:
1 Understand the experiment’s purpose.
2 Decide on the efficiency metric M to be measured and the

measurement unit (an operation’s count vs. a time unit).
3 Decide on characteristics of the input sample (its range, size, and

so on).
4 Prepare a program implementing the algorithm (or algorithms) for

the experimentation.
5 Generate a sample of inputs.
6 Run the algorithm (or algorithms) on the sample’s inputs and

record the data observed.
7 Analyse the data obtained.

(RMIT University) Algorithmic Analysis Lecture 2 64 / 74

Benchmarking Algorithms: Significance of input

The input and algorithm can be significant determinant of performance.

Thereotical: Merge-sort and Quick-sort have O(n log(n)) complexity,
while Selection-sort is O(n2).

Empirical: Running Times (in seconds) for different sorting algorithms
on a randomised list:

List size 500 2,500 10,000
Merge-Sort 0.8 8.1 39.8
Quick-Sort 0.3 1.3 5.3
Selection-Sort 1.5 35.0 534.7

For ordered lists for N = 2,500:

Random In Order In Reverse Order
Merge-Sort 8.1 7.8 7.9
Quick-Sort 1.3 35.1 37.1
Selection-Sort 35.0 34.4 35.3

(RMIT University) Algorithmic Analysis Lecture 2 65 / 74

Benchmarking Algorithms: Significance of input

The input and algorithm can be significant determinant of performance.

Thereotical: Merge-sort and Quick-sort have O(n log(n)) complexity,
while Selection-sort is O(n2).

Empirical: Running Times (in seconds) for different sorting algorithms
on a randomised list:

List size 500 2,500 10,000
Merge-Sort 0.8 8.1 39.8
Quick-Sort 0.3 1.3 5.3
Selection-Sort 1.5 35.0 534.7

For ordered lists for N = 2,500:

Random In Order In Reverse Order
Merge-Sort 8.1 7.8 7.9
Quick-Sort 1.3 35.1 37.1
Selection-Sort 35.0 34.4 35.3

(RMIT University) Algorithmic Analysis Lecture 2 65 / 74

Benchmarking Algorithms: Significance of input

The input and algorithm can be significant determinant of performance.

Thereotical: Merge-sort and Quick-sort have O(n log(n)) complexity,
while Selection-sort is O(n2).

Empirical: Running Times (in seconds) for different sorting algorithms
on a randomised list:

List size 500 2,500 10,000
Merge-Sort 0.8 8.1 39.8
Quick-Sort 0.3 1.3 5.3
Selection-Sort 1.5 35.0 534.7

For ordered lists for N = 2,500:

Random In Order In Reverse Order
Merge-Sort 8.1 7.8 7.9
Quick-Sort 1.3 35.1 37.1
Selection-Sort 35.0 34.4 35.3

(RMIT University) Algorithmic Analysis Lecture 2 65 / 74

Benchmarking Algorithms: Significance of input

The input and algorithm can be significant determinant of performance.

Thereotical: Merge-sort and Quick-sort have O(n log(n)) complexity,
while Selection-sort is O(n2).

Empirical: Running Times (in seconds) for different sorting algorithms
on a randomised list:

List size 500 2,500 10,000
Merge-Sort 0.8 8.1 39.8
Quick-Sort 0.3 1.3 5.3
Selection-Sort 1.5 35.0 534.7

For ordered lists for N = 2,500:

Random In Order In Reverse Order
Merge-Sort 8.1 7.8 7.9
Quick-Sort 1.3 35.1 37.1
Selection-Sort 35.0 34.4 35.3

(RMIT University) Algorithmic Analysis Lecture 2 65 / 74

Comparing Search Algorithms: Significance of input
size
The input size can be significant determinant of performance.

Thereotical: Linear search have O(n) complexity while binary search
have O(log(n)) complexity on a sorted list.

linear vs binary search

0.000

0.010

0.020

0.030

0.040

0.050

0 100
200

300
400

500
600

700
800

900
1,000

se
co

n
d

linear
binary

(RMIT University) Algorithmic Analysis Lecture 2 66 / 74

Comparing Search Algorithms: Significance of input
size
The input size can be significant determinant of performance.

Thereotical: Linear search have O(n) complexity while binary search
have O(log(n)) complexity on a sorted list.

linear vs binary search

0.000

0.010

0.020

0.030

0.040

0.050

0 100
200

300
400

500
600

700
800

900
1,000

se
co

n
d

linear
binary

(RMIT University) Algorithmic Analysis Lecture 2 66 / 74

Comparing Search Algorithms continued

linear vs binary search

0
500

1,000
1,500
2,000
2,500
3,000
3,500
4,000
4,500
5,000

0 250,000
500,000

750,000
1,000,000

se
co

nd
s linear
binary

(RMIT University) Algorithmic Analysis Lecture 2 67 / 74

Overview

1 Overview

2 Fundamentals

3 Asymptotic Complexity

4 Analysing Non-recursive Algorithms

5 Analysing Recursive Algorithms

6 Empirical Analysis

7 Rule of thumb Estimation of Complexity

8 Summary
(RMIT University) Algorithmic Analysis Lecture 2 68 / 74

Approximate Estimate of Complexity

• We can sometimes make an educated guess at the complexity,
then use theoretical and/or empirical analysis to comfirm.

• We discuss a few such guidelines here, but will discuss more as
we study further algorithms and data structures.
• Requires experience.

(RMIT University) Algorithmic Analysis Lecture 2 69 / 74

Approximate Estimate of Complexity

• We can sometimes make an educated guess at the complexity,
then use theoretical and/or empirical analysis to comfirm.

• We discuss a few such guidelines here, but will discuss more as
we study further algorithms and data structures.

• Requires experience.

(RMIT University) Algorithmic Analysis Lecture 2 69 / 74

Approximate Estimate of Complexity

• We can sometimes make an educated guess at the complexity,
then use theoretical and/or empirical analysis to comfirm.

• We discuss a few such guidelines here, but will discuss more as
we study further algorithms and data structures.
• Requires experience.

(RMIT University) Algorithmic Analysis Lecture 2 69 / 74

Constant time O(1)

• Typically algorithms or data structures whose operations does not
depend on input size.

• E.g., Access to an element in an array.

(RMIT University) Algorithmic Analysis Lecture 2 70 / 74

Constant time O(1)

• Typically algorithms or data structures whose operations does not
depend on input size.
• E.g., Access to an element in an array.

(RMIT University) Algorithmic Analysis Lecture 2 70 / 74

Linear time O(n)

• Typically algorithms or data structures whose operations that
needs to evaluate most or all of the elements of an problem (input
size).

• E.g., Scan through an array to search for an element.
• E.g., Copy elements from a linked list to another.
• In terms of pseudo code, it usually involves a single for loop.

(RMIT University) Algorithmic Analysis Lecture 2 71 / 74

Linear time O(n)

• Typically algorithms or data structures whose operations that
needs to evaluate most or all of the elements of an problem (input
size).
• E.g., Scan through an array to search for an element.

• E.g., Copy elements from a linked list to another.
• In terms of pseudo code, it usually involves a single for loop.

(RMIT University) Algorithmic Analysis Lecture 2 71 / 74

Linear time O(n)

• Typically algorithms or data structures whose operations that
needs to evaluate most or all of the elements of an problem (input
size).
• E.g., Scan through an array to search for an element.
• E.g., Copy elements from a linked list to another.

• In terms of pseudo code, it usually involves a single for loop.

(RMIT University) Algorithmic Analysis Lecture 2 71 / 74

Linear time O(n)

(RMIT University) Algorithmic Analysis Lecture 2 71 / 74

Quadratic time O(n2)

• Typically algorithms or data structures whose operations that
needs to process/evaluate pairs of elements of an problem.

• E.g., Compare each element in an array to all its others to find
duplicates (naive + unordered).

• E.g., Compute all pairwise distance among a set of points.
• In terms of pseudo code, it usually involves two nested for loops.

(RMIT University) Algorithmic Analysis Lecture 2 72 / 74

Quadratic time O(n2)

• Typically algorithms or data structures whose operations that
needs to process/evaluate pairs of elements of an problem.
• E.g., Compare each element in an array to all its others to find

duplicates (naive + unordered).

• E.g., Compute all pairwise distance among a set of points.
• In terms of pseudo code, it usually involves two nested for loops.

(RMIT University) Algorithmic Analysis Lecture 2 72 / 74

Quadratic time O(n2)

• Typically algorithms or data structures whose operations that
needs to process/evaluate pairs of elements of an problem.
• E.g., Compare each element in an array to all its others to find

duplicates (naive + unordered).
• E.g., Compute all pairwise distance among a set of points.

• In terms of pseudo code, it usually involves two nested for loops.

(RMIT University) Algorithmic Analysis Lecture 2 72 / 74

Quadratic time O(n2)

• Typically algorithms or data structures whose operations that
needs to process/evaluate pairs of elements of an problem.
• E.g., Compare each element in an array to all its others to find

duplicates (naive + unordered).
• E.g., Compute all pairwise distance among a set of points.
• In terms of pseudo code, it usually involves two nested for loops.

(RMIT University) Algorithmic Analysis Lecture 2 72 / 74

Overview

1 Overview

2 Fundamentals

3 Asymptotic Complexity

4 Analysing Non-recursive Algorithms

5 Analysing Recursive Algorithms

6 Empirical Analysis

7 Rule of thumb Estimation of Complexity

8 Summary
(RMIT University) Algorithmic Analysis Lecture 2 73 / 74

Summary

• We have covered the core theoretical framework for algorithmic
analysis which will be used for the rest of the semester.
• Problem input size, basic operation, time complexity, asymptotic

complexity, worst/best/average cases.
• Analysis of Non-recursive, recursive algorithms.
• Empirical analysis.
• Approximate analysis.

Next week, we look at first of the algorithmic paradigms in this course,
brute force algorithms.

(RMIT University) Algorithmic Analysis Lecture 2 74 / 74

Overview
Fundamentals
Asymptotic Complexity
Analysing Non-recursive Algorithms
Analysing Recursive Algorithms
Empirical Analysis
Rule of thumb Estimation of Complexity
Summary

Related Posts