Correctness

Time Complexity

Chapter 2
Algorithm Analysis: Correctness and Running Time

Philip W. L. Fong

Department of Computer Science

University of Calgary
Calgary, Alberta, Canada

CPSC 331 (Fall 2025)

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Course Overview

Part 1: Foundations Part 2: Dynamic Sets

Correctness Stacks and Queues
Running Time Analysis / Linked Lists
Divide-and-Conquer Trees
Sorting Binary Search Trees
Searching Red-Black Trees

Part 4: Graph Algorithms 

Representation of Graphs Part 3: Probabilistic Analysis
Breadth-First Search o Indicator Random Variables
Depth-First Search Quicksort
Dijkstra’s Algorithm Hash Tables
Prim’s Algorithm

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Readings

Chapter 2: Getting Started

§2.1: Insertion Sort
§2.2: Analyzing Algorithms

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Example of Problem/Instance
Example (Sorting)
The sorting problem can be stated as follows:
Input: a sequence ⟨a1 , a2 , . . . an ⟩ of “keys”
The keys are assumed to be comparable (i.e., supporting
the < operator, which is a binary relation that is irreflexive,
asymmetric, and transitive).
Output: a permutation ⟨b1 , b2 , . . . , bn ⟩ of the input
sequence that is in ascending order
Here is an instance of the sorting problem:

⟨3, 1, 4, 2, 5⟩

The expected output would be the following:

⟨1, 2, 3, 4, 5⟩
Philip W. L. Fong Chapter 2: Algorithm Analysis
 Correctness
Time Complexity

Insertion Sort (1)

Algorithm 1: I NSERTION -S ORT(A)
1 for j = 2 to [Link] do
2 key = A[j];
3 Insert key into the sorted subarray A[1 .. j − 1];

key
ii
I
j
sorted prefix
wtf
processed
Philip W. L. Fong Chapter 2: Algorithm Analysis
 Correctness
Time Complexity

Insertion Sort (2)

Algorithm 2: I NSERTION -S ORT(A)

1 for j = 2 to [Link] do
2 key = A[j];
// Insert key into the sorted subarray A[1 .. j − 1].
3 i = j − 1;
4 while i > 0 and A[i] > key do
5 A[i + 1] = A[i];
6 i = i − 1;
7 A[i + 1] = key ;

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Algorithm Analysis

Once we have designed an algorithm to solve a computational

problem, we need to perform 2 kinds of analysis
Correctness
Does the algorithm really “solve” the computational
problem?
Complexity
How efficient is the algorithm (in terms of resource
consumption)?
time (our focus in this course)
space (aka memory)
synchronization steps
communication operations
random bits
etc

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Outline

1 Correctness

2 Time Complexity

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Keyword: “solve”

By saying that an algorithm A solves a computational

problem P, it means that, if A is given inputs that satisfy
the input specification of P, then it is guaranteed that A will
(a) terminate in finite time and (b) produce results that
satisfy the output specification of P.

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Keyword: “solve”

By saying that an algorithm A solves a computational

problem P, it means that, if A is given inputs that satisfy
the input specification of P, then it is guaranteed that A will
(a) terminate in finite time and (b) produce results that
satisfy the output specification of P.

Definition (Total Correctness)

Total Correctness = Termination + Partial Correctness

Assuming that the input match the parameter description:
Termination: The algorithm terminates in finite time.
Partial Correctness: On termination, the algorithm
produces results that satisfy the result specification.

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Preparing To Prove Partial Correctness

We will learn to establish partial correctness by using loop
invariants.
Problem: It is easier to work with while-loops than
for-loops.

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Preparing To Prove Partial Correctness

We will learn to establish partial correctness by using loop
invariants.
Problem: It is easier to work with while-loops than
for-loops.
Algorithm 5: A for-loop.
1 for i = m to n do
2 do something;

Algorithm 6: An equivalent while-loop.

1 i = m;
2 while i ≤ n do
3 do something;
4 i = i + 1;

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Insertion Sort via While-Loop

Algorithm 7: I NSERTION -S ORT(A)

1 for j = 2 to [Link] do
2 key = A[j];
3 Insert key into the sorted subarray A[1 .. j − 1];

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Insertion Sort via While-Loop

Algorithm 9: I NSERTION -S ORT(A)

1 for j = 2 to [Link] do
2 key = A[j];
3 Insert key into the sorted subarray A[1 .. j − 1];

Algorithm 10: I NSERTION -S ORT(A)

1 j = 2;
2 while j ≤ [Link] do
3 key = A[j];
4 Insert key into the sorted subarray A[1 .. j − 1];
5 j = j + 1;

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Proving Partial Correctness

Definition (Loop Invariant)

A condition P is a loop invariant for a loop if the following hold.
Initialization. Condition P is established when the loop is
first entered.
Maintenance. If condition P holds in the beginning of an
iteration, then P is reestablished at the end of that iteration.
An immediate corollary is the following.
Termination. The condition P holds if and when the loop
terminates.

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Loop Invariant for Insertion Sort

Conjecture
The following are loop invariants of Insertion Sort:
1 Each of A[1..j − 1] and A[j..n] contains the elements
originally residing in that subarray when I NSERTION -S ORT
was first invoked (but perhaps in a different order).
2 A[1..j − 1] is sorted.

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Loop Invariant for Insertion Sort

Conjecture
The following are loop invariants of Insertion Sort:
1 Each of A[1..j − 1] and A[j..n] contains the elements
originally residing in that subarray when I NSERTION -S ORT
was first invoked (but perhaps in a different order).
2 A[1..j − 1] is sorted.

Corollary
If and when the while-loop terminates, j = n + 1. The loop
invariants imply the following:
1 A[1..n] contains the elements originally residing in that
subarray when I NSERTION -S ORT was first invoked (but
perhaps in a different order).
2 A[1..n] is sorted.
Philip W. L. Fong Chapter 2: Algorithm Analysis
 Correctness
Time Complexity

Establishing Partial Correctness

1 Conjecture a condition P to be the loop invariant.

Typically, the algorithm is designed with that loop invariant
in mind.
2 Prove that P really is a loop invariant.
Initialization. Prove that condition P is established when
the loop is first entered.
Maintenance. Prove the following implication: If condition
P holds in the beginning of an iteration, then P is
reestablished at the end of that iteration.
3 Conclude that P holds when the loop terminates.
Typically P is the property we want at termination.
This informs the conjecture of P above.

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Loop Invariant for General Loop

Algorithm 11: A general loop.

1 initialize variables;
// Initialization: P should hold here.
2 while C do
// Maintenance (part 1): If P holds here, . . .
3 do something;
// Maintenance (part 2): . . . then P should hold here.
// Termination: Conclude that both P and ¬C hold here if
the loop terminates.

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Assertions

The conditions specified the comments are called

assertions.
They are conditions that are intended to be true at the time
control flows pass them.
When an assertion is made in pseudocode, it needs to be
established mathematically.

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Insertion Sort via While-Loop

Algorithm 12: I NSERTION -S ORT(A)

1 j = 2;
2 while j ≤ [Link] do
3 key = A[j];
4 Insert key into the sorted subarray A[1 .. j − 1];
5 j = j + 1;

key
ii
I
j
sorted prefix
wtf
processed

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Partial Correctness of Insertion Sort

Loop Invariant: A[1..j − 1] is sorted.

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Partial Correctness of Insertion Sort

Loop Invariant: A[1..j − 1] is sorted.

Initialization: Once j is initialized to 2, the subarray
A[1..j − 1] is indeed sorted because there is only one
element in A[1..1].

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Partial Correctness of Insertion Sort

Loop Invariant: A[1..j − 1] is sorted.

Initialization: Once j is initialized to 2, the subarray
A[1..j − 1] is indeed sorted because there is only one
element in A[1..1].
Maintenance:
Suppose A[1..j − 1] is sorted at the beginning of an
iteration.
Let j0 be the value stored in variable j at that time.
A[j0 ] is then inserted into A[1..j0 − 1], with overflow element
shifted to A[j0 ].
A[1..j0 ] is now sorted.
After j is incremented from j0 to j0 + 1, the condition
“A[1..j − 1] is sorted” becomes true again.

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Exercise

Show that the following is a loop invariant of

I NSERTION -S ORT:
Each of A[1..j − 1] and A[j..n] contains the elements
originally residing in that subarray when I NSERTION -S ORT
was first invoked (but perhaps in a different order).

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Outline

1 Correctness

2 Time Complexity

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Time Complexity
What shall we “count” when we evaluate the running time?
abstract computational steps
typically the ones that are the most expensive

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Time Complexity
What shall we “count” when we evaluate the running time?
abstract computational steps
typically the ones that are the most expensive
In the case of Insertion Sort: key comparisons

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Time Complexity
What shall we “count” when we evaluate the running time?
abstract computational steps
typically the ones that are the most expensive
In the case of Insertion Sort: key comparisons
In other cases, it could be:
expensive arithmetic operations (e.g., multiplication)
data movement (assignment statements)
certain API calls (database queries)

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Time Complexity
What shall we “count” when we evaluate the running time?
abstract computational steps
typically the ones that are the most expensive
In the case of Insertion Sort: key comparisons
In other cases, it could be:
expensive arithmetic operations (e.g., multiplication)
data movement (assignment statements)
certain API calls (database queries)
Expressed as a function of the input size.
Example: for an input array of size n, the number of key
comparisons is:

T (n) = n(n − 1)/2.

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Time Complexity
What shall we “count” when we evaluate the running time?
abstract computational steps
typically the ones that are the most expensive
In the case of Insertion Sort: key comparisons
In other cases, it could be:
expensive arithmetic operations (e.g., multiplication)
data movement (assignment statements)
certain API calls (database queries)
Expressed as a function of the input size.
Example: for an input array of size n, the number of key
comparisons is:

T (n) = n(n − 1)/2.

As we shall see later, what algorithm designers care most

about is the growth rate of T (n).
The order of growth is the n2 term in T (n).
Philip W. L. Fong Chapter 2: Algorithm Analysis
 Correctness
Time Complexity

Insertion Sort (2)

Algorithm 13: I NSERTION -S ORT(A)

1 for j = 2 to [Link] do
2 key = A[j];
// Insert key into the sorted subarray A[1 .. j − 1].
3 i = j − 1;
4 while i > 0 and A[i] > key do
5 A[i + 1] = A[i];
6 i = i − 1;
7 A[i + 1] = key ;

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Running Time of Insertion Sort

Let n be the length of the input array

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Running Time of Insertion Sort

Let n be the length of the input array
Outer loop: from 2 to n
n
X
(cost of inner loop)
j=2

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Running Time of Insertion Sort

Let n be the length of the input array
Outer loop: from 2 to n
n
X
(cost of inner loop)
j=2

Inner loop (worst case): from j − 1 to 1

n
X
(j − 1)
j=2

= 1 + 2 + . . . + (n − 1)
(1 + (n − 1)) × (n − 1)
=
2
n(n − 1)
=
2

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Running Time of Insertion Sort

Let n be the length of the input array
Outer loop: from 2 to n
n
X
(cost of inner loop)
j=2

Inner loop (worst case): from j − 1 to 1

n
X
(j − 1)
j=2

= 1 + 2 + . . . + (n − 1)
(1 + (n − 1)) × (n − 1)
=
2
n(n − 1)
=
2

Running time (in number of comparisons): n(n − 1)/2

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Insertion Sort (2)

Algorithm 14: I NSERTION -S ORT(A)

1 for j = 2 to [Link] do
2 key = A[j];
// Insert key into the sorted subarray A[1 .. j − 1].
3 i = j − 1;
4 while i > 0 and A[i] > key do
5 A[i + 1] = A[i];
6 i = i − 1;
7 A[i + 1] = key ;

Philip W. L. Fong Chapter 2: Algorithm Analysis

 Correctness
Time Complexity

Worst- vs Best-Case Running Time

Worst-case: Input array is reverse-sorted, causing

insertion to be always at the front of the sorted prefix.

n(n − 1)/2

Best-case: Input array is sorted, causing insertion to be

always at the end of the sorted prefix.

n−1

We are mostly concerned with the worst-case running time.

Philip W. L. Fong Chapter 2: Algorithm Analysis