Discrete Mathematics

Chapter 3: The Fundamentals: Algorithms, the Integers

Department of Mathematics
The FPT university

TrungDT (FUHN) MAD101 Chapter 3 1 / 45

Chapter 3: Introduction

TrungDT (FUHN) MAD101 Chapter 3 2 / 45

Chapter 3: Introduction

Topics covered:

TrungDT (FUHN) MAD101 Chapter 3 2 / 45

Chapter 3: Introduction

Topics covered:

3.1 Algorithms

TrungDT (FUHN) MAD101 Chapter 3 2 / 45

Chapter 3: Introduction

Topics covered:

3.1 Algorithms
3.2 The Growth of Functions

TrungDT (FUHN) MAD101 Chapter 3 2 / 45

Chapter 3: Introduction

Topics covered:

3.1 Algorithms
3.2 The Growth of Functions
3.3 Complexity of Algorithms

TrungDT (FUHN) MAD101 Chapter 3 2 / 45

Chapter 3: Introduction

Topics covered:

3.1 Algorithms
3.2 The Growth of Functions
3.3 Complexity of Algorithms
3.4 The Integers and Division

TrungDT (FUHN) MAD101 Chapter 3 2 / 45

Chapter 3: Introduction

Topics covered:

3.1 Algorithms
3.2 The Growth of Functions
3.3 Complexity of Algorithms
3.4 The Integers and Division
3.5 Primes and Greatest Common Divisors

TrungDT (FUHN) MAD101 Chapter 3 2 / 45

Chapter 3: Introduction

Topics covered:

3.1 Algorithms
3.2 The Growth of Functions
3.3 Complexity of Algorithms
3.4 The Integers and Division
3.5 Primes and Greatest Common Divisors
3.6 Integers and Algorithms

TrungDT (FUHN) MAD101 Chapter 3 2 / 45

3.1 Algorithms

TrungDT (FUHN) MAD101 Chapter 3 3 / 45

3.1 Algorithms

TrungDT (FUHN) MAD101 Chapter 3 3 / 45

3.1 Algorithms

An algorithm is a finite set of precise instructions for performing a

computation or for solving a problem.

TrungDT (FUHN) MAD101 Chapter 3 3 / 45

3.1 Algorithms

An algorithm is a finite set of precise instructions for performing a

computation or for solving a problem.

Example. Describe an algorithm to solve quadratic equations.

TrungDT (FUHN) MAD101 Chapter 3 3 / 45

3.1 Algorithms

An algorithm is a finite set of precise instructions for performing a

computation or for solving a problem.

Example. Describe an algorithm to solve quadratic equations.

Input. a, b, c : integers (coefficients)

Output. Solutions if they exist.

Step 1. If a = 0 then Print (This is not a quadratic equation).

Step 2. Compute ∆ = b 2 − 4ac
Step 3. If ∆ < 0 then Print (No solution).
Step 4. If ∆ = 0, compute x = −b/2a
Step 5. If ∆ > 0, compute
√ √
x1 = (−b + ∆)/(2a), x2 = (−b − ∆)/(2a)

TrungDT (FUHN) MAD101 Chapter 3 3 / 45

TrungDT (FUHN) MAD101 Chapter 3 4 / 45
Properties of Algorithms:

TrungDT (FUHN) MAD101 Chapter 3 4 / 45

Properties of Algorithms:

Input:

TrungDT (FUHN) MAD101 Chapter 3 4 / 45

Properties of Algorithms:

Input: An algorithm has input values from a specified set.

TrungDT (FUHN) MAD101 Chapter 3 4 / 45

Properties of Algorithms:

Input: An algorithm has input values from a specified set.

Output:

TrungDT (FUHN) MAD101 Chapter 3 4 / 45

Properties of Algorithms:

Input: An algorithm has input values from a specified set.

Output: From each set of input values an algorithm produces output
values from a specified set, and they are solutions to the problem.

TrungDT (FUHN) MAD101 Chapter 3 4 / 45

Properties of Algorithms:

Input: An algorithm has input values from a specified set.

Output: From each set of input values an algorithm produces output
values from a specified set, and they are solutions to the problem.
Definiteness:

TrungDT (FUHN) MAD101 Chapter 3 4 / 45

Properties of Algorithms:

Input: An algorithm has input values from a specified set.

Output: From each set of input values an algorithm produces output
values from a specified set, and they are solutions to the problem.
Definiteness: The steps of an algorithm must be defined precisely.

TrungDT (FUHN) MAD101 Chapter 3 4 / 45

Properties of Algorithms:

Input: An algorithm has input values from a specified set.

Output: From each set of input values an algorithm produces output
values from a specified set, and they are solutions to the problem.
Definiteness: The steps of an algorithm must be defined precisely.
Correctness:

TrungDT (FUHN) MAD101 Chapter 3 4 / 45

Properties of Algorithms:

Input: An algorithm has input values from a specified set.

Output: From each set of input values an algorithm produces output
values from a specified set, and they are solutions to the problem.
Definiteness: The steps of an algorithm must be defined precisely.
Correctness: An algorithm should produce the correct output values
for each set of input values.

TrungDT (FUHN) MAD101 Chapter 3 4 / 45

Properties of Algorithms:

Input: An algorithm has input values from a specified set.

Output: From each set of input values an algorithm produces output
values from a specified set, and they are solutions to the problem.
Definiteness: The steps of an algorithm must be defined precisely.
Correctness: An algorithm should produce the correct output values
for each set of input values.
Finiteness:

TrungDT (FUHN) MAD101 Chapter 3 4 / 45

Properties of Algorithms:

Input: An algorithm has input values from a specified set.

Output: From each set of input values an algorithm produces output
values from a specified set, and they are solutions to the problem.
Definiteness: The steps of an algorithm must be defined precisely.
Correctness: An algorithm should produce the correct output values
for each set of input values.
Finiteness: An algorithm should produce the desired output after a
finite number of steps.

TrungDT (FUHN) MAD101 Chapter 3 4 / 45

Properties of Algorithms:

Input: An algorithm has input values from a specified set.

Output: From each set of input values an algorithm produces output
values from a specified set, and they are solutions to the problem.
Definiteness: The steps of an algorithm must be defined precisely.
Correctness: An algorithm should produce the correct output values
for each set of input values.
Finiteness: An algorithm should produce the desired output after a
finite number of steps.
Effectiveness::

TrungDT (FUHN) MAD101 Chapter 3 4 / 45

Properties of Algorithms:

Input: An algorithm has input values from a specified set.

Output: From each set of input values an algorithm produces output
values from a specified set, and they are solutions to the problem.
Definiteness: The steps of an algorithm must be defined precisely.
Correctness: An algorithm should produce the correct output values
for each set of input values.
Finiteness: An algorithm should produce the desired output after a
finite number of steps.
Effectiveness:: It must be possible to perform each step of an
algorithm exactly and in a finite amount of time.

TrungDT (FUHN) MAD101 Chapter 3 4 / 45

Properties of Algorithms:

Input: An algorithm has input values from a specified set.

Output: From each set of input values an algorithm produces output
values from a specified set, and they are solutions to the problem.
Definiteness: The steps of an algorithm must be defined precisely.
Correctness: An algorithm should produce the correct output values
for each set of input values.
Finiteness: An algorithm should produce the desired output after a
finite number of steps.
Effectiveness:: It must be possible to perform each step of an
algorithm exactly and in a finite amount of time.
Generality:

TrungDT (FUHN) MAD101 Chapter 3 4 / 45

Properties of Algorithms:

Input: An algorithm has input values from a specified set.

Output: From each set of input values an algorithm produces output
values from a specified set, and they are solutions to the problem.
Definiteness: The steps of an algorithm must be defined precisely.
Correctness: An algorithm should produce the correct output values
for each set of input values.
Finiteness: An algorithm should produce the desired output after a
finite number of steps.
Effectiveness:: It must be possible to perform each step of an
algorithm exactly and in a finite amount of time.
Generality: Algorithm should be applicable for all problems of the
desired form, not just a particular set of input values.

TrungDT (FUHN) MAD101 Chapter 3 4 / 45

Some Algorithms

TrungDT (FUHN) MAD101 Chapter 3 5 / 45

Some Algorithms

Find maximum element of a finite sequence

TrungDT (FUHN) MAD101 Chapter 3 5 / 45

Some Algorithms

Find maximum element of a finite sequence

Searching algorithms:

TrungDT (FUHN) MAD101 Chapter 3 5 / 45

Some Algorithms

Find maximum element of a finite sequence

Searching algorithms:
Linear search algorithm

TrungDT (FUHN) MAD101 Chapter 3 5 / 45

Some Algorithms

Find maximum element of a finite sequence

Searching algorithms:
Linear search algorithm
Binary search algorithm

TrungDT (FUHN) MAD101 Chapter 3 5 / 45

Some Algorithms

Find maximum element of a finite sequence

Searching algorithms:
Linear search algorithm
Binary search algorithm
Sorting algorithms:

TrungDT (FUHN) MAD101 Chapter 3 5 / 45

Some Algorithms

Find maximum element of a finite sequence

Searching algorithms:
Linear search algorithm
Binary search algorithm
Sorting algorithms:
Bubble sort

TrungDT (FUHN) MAD101 Chapter 3 5 / 45

Some Algorithms

Find maximum element of a finite sequence

Searching algorithms:
Linear search algorithm
Binary search algorithm
Sorting algorithms:
Bubble sort
Insertion sort

TrungDT (FUHN) MAD101 Chapter 3 5 / 45

Some Algorithms

Find maximum element of a finite sequence

Searching algorithms:
Linear search algorithm
Binary search algorithm
Sorting algorithms:
Bubble sort
Insertion sort

TrungDT (FUHN) MAD101 Chapter 3 5 / 45

Some Algorithms

Find maximum element of a finite sequence

Searching algorithms:
Linear search algorithm
Binary search algorithm
Sorting algorithms:
Bubble sort
Insertion sort
Greedy change-making algorithm.

TrungDT (FUHN) MAD101 Chapter 3 5 / 45

Some Algorithms

Find maximum element of a finite sequence

Searching algorithms:
Linear search algorithm
Binary search algorithm
Sorting algorithms:
Bubble sort
Insertion sort
Greedy change-making algorithm.

TrungDT (FUHN) MAD101 Chapter 3 5 / 45

Finding Maximum Element

TrungDT (FUHN) MAD101 Chapter 3 6 / 45

Finding Maximum Element

Input: Sequence of integers a1 , a2 , . . . , an

TrungDT (FUHN) MAD101 Chapter 3 6 / 45

Finding Maximum Element

Input: Sequence of integers a1 , a2 , . . . , an

Output: The maximum number of the sequence

TrungDT (FUHN) MAD101 Chapter 3 6 / 45

Finding Maximum Element

Input: Sequence of integers a1 , a2 , . . . , an

Output: The maximum number of the sequence

TrungDT (FUHN) MAD101 Chapter 3 6 / 45

Finding Maximum Element

Input: Sequence of integers a1 , a2 , . . . , an

Output: The maximum number of the sequence

Algorithm:

TrungDT (FUHN) MAD101 Chapter 3 6 / 45

Finding Maximum Element

Input: Sequence of integers a1 , a2 , . . . , an

Output: The maximum number of the sequence

Algorithm:

Step 1. Set the temporary maximum be the first element.

TrungDT (FUHN) MAD101 Chapter 3 6 / 45

Finding Maximum Element

Input: Sequence of integers a1 , a2 , . . . , an

Output: The maximum number of the sequence

Algorithm:

Step 1. Set the temporary maximum be the first element.

Step 2. Compare the temporary maximum to the next element, if this
element is larger then set the temporary maximum to be this integer.

TrungDT (FUHN) MAD101 Chapter 3 6 / 45

Finding Maximum Element

Input: Sequence of integers a1 , a2 , . . . , an

Output: The maximum number of the sequence

Algorithm:

Step 1. Set the temporary maximum be the first element.

Step 2. Compare the temporary maximum to the next element, if this
element is larger then set the temporary maximum to be this integer.
Step 3. Repeat Step 2 if there are more integers in the sequence.

TrungDT (FUHN) MAD101 Chapter 3 6 / 45

Finding Maximum Element

Input: Sequence of integers a1 , a2 , . . . , an

Output: The maximum number of the sequence

Algorithm:

Step 1. Set the temporary maximum be the first element.

Step 2. Compare the temporary maximum to the next element, if this
element is larger then set the temporary maximum to be this integer.
Step 3. Repeat Step 2 if there are more integers in the sequence.
Step 4. Stop the algorithm when there are no integers left. The
temporary maximum at this point is the maximum of the sequence.

TrungDT (FUHN) MAD101 Chapter 3 6 / 45

Finding Maximum Element

Input: Sequence of integers a1 , a2 , . . . , an

Output: The maximum number of the sequence

Algorithm:

Step 1. Set the temporary maximum be the first element.

Step 2. Compare the temporary maximum to the next element, if this
element is larger then set the temporary maximum to be this integer.
Step 3. Repeat Step 2 if there are more integers in the sequence.
Step 4. Stop the algorithm when there are no integers left. The
temporary maximum at this point is the maximum of the sequence.

TrungDT (FUHN) MAD101 Chapter 3 6 / 45

TrungDT (FUHN) MAD101 Chapter 3 7 / 45
Procedure Max(a1 , a2 , . . . , an : integers)

TrungDT (FUHN) MAD101 Chapter 3 7 / 45

Procedure Max(a1 , a2 , . . . , an : integers)
max := a1

TrungDT (FUHN) MAD101 Chapter 3 7 / 45

Procedure Max(a1 , a2 , . . . , an : integers)
max := a1
for i := 2 to n

TrungDT (FUHN) MAD101 Chapter 3 7 / 45

Procedure Max(a1 , a2 , . . . , an : integers)
max := a1
for i := 2 to n
if max < ai then max := ai

TrungDT (FUHN) MAD101 Chapter 3 7 / 45

Procedure Max(a1 , a2 , . . . , an : integers)
max := a1
for i := 2 to n
if max < ai then max := ai

TrungDT (FUHN) MAD101 Chapter 3 7 / 45

Linear Search

TrungDT (FUHN) MAD101 Chapter 3 8 / 45

Linear Search

Input: A sequence of distinct integers a1 , a2 , . . . , an , and an integer x

TrungDT (FUHN) MAD101 Chapter 3 8 / 45

Linear Search

Input: A sequence of distinct integers a1 , a2 , . . . , an , and an integer x

Output: The location of x in the sequence (is 0 if x is not in the
sequence)

TrungDT (FUHN) MAD101 Chapter 3 8 / 45

Linear Search

Input: A sequence of distinct integers a1 , a2 , . . . , an , and an integer x

Output: The location of x in the sequence (is 0 if x is not in the
sequence)

Algorithm:

TrungDT (FUHN) MAD101 Chapter 3 8 / 45

Linear Search

Input: A sequence of distinct integers a1 , a2 , . . . , an , and an integer x

Output: The location of x in the sequence (is 0 if x is not in the
sequence)

Algorithm: Compare x successively to each term of the sequence until a

match is found.

TrungDT (FUHN) MAD101 Chapter 3 8 / 45

Linear Search

Input: A sequence of distinct integers a1 , a2 , . . . , an , and an integer x

Output: The location of x in the sequence (is 0 if x is not in the
sequence)

Algorithm: Compare x successively to each term of the sequence until a

match is found.

Procedure LinearSearch (a1 , a2 , . . . , an : distinct integers, x: integer)

TrungDT (FUHN) MAD101 Chapter 3 8 / 45

Linear Search

Input: A sequence of distinct integers a1 , a2 , . . . , an , and an integer x

Output: The location of x in the sequence (is 0 if x is not in the
sequence)

Algorithm: Compare x successively to each term of the sequence until a

match is found.

Procedure LinearSearch (a1 , a2 , . . . , an : distinct integers, x: integer)

i := 1

TrungDT (FUHN) MAD101 Chapter 3 8 / 45

Linear Search

Input: A sequence of distinct integers a1 , a2 , . . . , an , and an integer x

Output: The location of x in the sequence (is 0 if x is not in the
sequence)

Algorithm: Compare x successively to each term of the sequence until a

match is found.

Procedure LinearSearch (a1 , a2 , . . . , an : distinct integers, x: integer)

i := 1
while (i ≤ n) and (x 6= ai )

TrungDT (FUHN) MAD101 Chapter 3 8 / 45

Linear Search

Input: A sequence of distinct integers a1 , a2 , . . . , an , and an integer x

Output: The location of x in the sequence (is 0 if x is not in the
sequence)

Algorithm: Compare x successively to each term of the sequence until a

match is found.

Procedure LinearSearch (a1 , a2 , . . . , an : distinct integers, x: integer)

i := 1
while (i ≤ n) and (x 6= ai )
i := i + 1

TrungDT (FUHN) MAD101 Chapter 3 8 / 45

Linear Search

Input: A sequence of distinct integers a1 , a2 , . . . , an , and an integer x

Output: The location of x in the sequence (is 0 if x is not in the
sequence)

Algorithm: Compare x successively to each term of the sequence until a

match is found.

Procedure LinearSearch (a1 , a2 , . . . , an : distinct integers, x: integer)

i := 1
while (i ≤ n) and (x 6= ai )
i := i + 1
if i ≤ n then location := i

TrungDT (FUHN) MAD101 Chapter 3 8 / 45

Linear Search

Input: A sequence of distinct integers a1 , a2 , . . . , an , and an integer x

Output: The location of x in the sequence (is 0 if x is not in the
sequence)

Algorithm: Compare x successively to each term of the sequence until a

match is found.

Procedure LinearSearch (a1 , a2 , . . . , an : distinct integers, x: integer)

i := 1
while (i ≤ n) and (x 6= ai )
i := i + 1
if i ≤ n then location := i
else location := 0

TrungDT (FUHN) MAD101 Chapter 3 8 / 45

TrungDT (FUHN) MAD101 Chapter 3 9 / 45
TrungDT (FUHN) MAD101 Chapter 3 9 / 45
Binary Search

TrungDT (FUHN) MAD101 Chapter 3 10 / 45

Binary Search
Input: An increasing sequence of integers a1 < a2 < · · · < an and an
integer x

TrungDT (FUHN) MAD101 Chapter 3 10 / 45

Binary Search
Input: An increasing sequence of integers a1 < a2 < · · · < an and an
integer x
Output: The location of x in the sequence (is 0 if x is not in the
sequence)

TrungDT (FUHN) MAD101 Chapter 3 10 / 45

Binary Search
Input: An increasing sequence of integers a1 < a2 < · · · < an and an
integer x
Output: The location of x in the sequence (is 0 if x is not in the
sequence)

Algorithm:

TrungDT (FUHN) MAD101 Chapter 3 10 / 45

Binary Search
Input: An increasing sequence of integers a1 < a2 < · · · < an and an
integer x
Output: The location of x in the sequence (is 0 if x is not in the
sequence)

Algorithm: Compare x to the element at the middle of the list, then

restrict the search to either the sublist on the left or the sublist on the
right.

TrungDT (FUHN) MAD101 Chapter 3 10 / 45

Binary Search
Input: An increasing sequence of integers a1 < a2 < · · · < an and an
integer x
Output: The location of x in the sequence (is 0 if x is not in the
sequence)

Algorithm: Compare x to the element at the middle of the list, then

restrict the search to either the sublist on the left or the sublist on the
right.

Procedure BinarySearch(a1 < a2 < . . . < an , x: integers)

TrungDT (FUHN) MAD101 Chapter 3 10 / 45

Binary Search
Input: An increasing sequence of integers a1 < a2 < · · · < an and an
integer x
Output: The location of x in the sequence (is 0 if x is not in the
sequence)

Algorithm: Compare x to the element at the middle of the list, then

restrict the search to either the sublist on the left or the sublist on the
right.

Procedure BinarySearch(a1 < a2 < . . . < an , x: integers)

i := 1, j := n

TrungDT (FUHN) MAD101 Chapter 3 10 / 45

Binary Search
Input: An increasing sequence of integers a1 < a2 < · · · < an and an
integer x
Output: The location of x in the sequence (is 0 if x is not in the
sequence)

Algorithm: Compare x to the element at the middle of the list, then

restrict the search to either the sublist on the left or the sublist on the
right.

Procedure BinarySearch(a1 < a2 < . . . < an , x: integers)

i := 1, j := n
while (i < j)

TrungDT (FUHN) MAD101 Chapter 3 10 / 45

Binary Search
Input: An increasing sequence of integers a1 < a2 < · · · < an and an
integer x
Output: The location of x in the sequence (is 0 if x is not in the
sequence)

Algorithm: Compare x to the element at the middle of the list, then

restrict the search to either the sublist on the left or the sublist on the
right.

Procedure BinarySearch(a1 < a2 < . . . < an , x: integers)

i := 1, j := n
while (i < j)
m := b(i + j)/2c

TrungDT (FUHN) MAD101 Chapter 3 10 / 45

Binary Search
Input: An increasing sequence of integers a1 < a2 < · · · < an and an
integer x
Output: The location of x in the sequence (is 0 if x is not in the
sequence)

Algorithm: Compare x to the element at the middle of the list, then

restrict the search to either the sublist on the left or the sublist on the
right.

Procedure BinarySearch(a1 < a2 < . . . < an , x: integers)

i := 1, j := n
while (i < j)
m := b(i + j)/2c
if x > am then i := m + 1

TrungDT (FUHN) MAD101 Chapter 3 10 / 45

Binary Search
Input: An increasing sequence of integers a1 < a2 < · · · < an and an
integer x
Output: The location of x in the sequence (is 0 if x is not in the
sequence)

Algorithm: Compare x to the element at the middle of the list, then

restrict the search to either the sublist on the left or the sublist on the
right.

Procedure BinarySearch(a1 < a2 < . . . < an , x: integers)

i := 1, j := n
while (i < j)
m := b(i + j)/2c
if x > am then i := m + 1
else j := m

TrungDT (FUHN) MAD101 Chapter 3 10 / 45

Binary Search
Input: An increasing sequence of integers a1 < a2 < · · · < an and an
integer x
Output: The location of x in the sequence (is 0 if x is not in the
sequence)

Algorithm: Compare x to the element at the middle of the list, then

restrict the search to either the sublist on the left or the sublist on the
right.

Procedure BinarySearch(a1 < a2 < . . . < an , x: integers)

i := 1, j := n
while (i < j)
m := b(i + j)/2c
if x > am then i := m + 1
else j := m
if x = ai then location := i

TrungDT (FUHN) MAD101 Chapter 3 10 / 45

Binary Search
Input: An increasing sequence of integers a1 < a2 < · · · < an and an
integer x
Output: The location of x in the sequence (is 0 if x is not in the
sequence)

Algorithm: Compare x to the element at the middle of the list, then

restrict the search to either the sublist on the left or the sublist on the
right.

Procedure BinarySearch(a1 < a2 < . . . < an , x: integers)

i := 1, j := n
while (i < j)
m := b(i + j)/2c
if x > am then i := m + 1
else j := m
if x = ai then location := i
else location := 0
TrungDT (FUHN) MAD101 Chapter 3 10 / 45
TrungDT (FUHN) MAD101 Chapter 3 11 / 45
TrungDT (FUHN) MAD101 Chapter 3 11 / 45
Bubble Sort

TrungDT (FUHN) MAD101 Chapter 3 12 / 45

Bubble Sort

Input: A sequence of integers a1 , a2 , . . . , an

TrungDT (FUHN) MAD101 Chapter 3 12 / 45

Bubble Sort

Input: A sequence of integers a1 , a2 , . . . , an

Output: The sequence in the increasing order

TrungDT (FUHN) MAD101 Chapter 3 12 / 45

Bubble Sort

Input: A sequence of integers a1 , a2 , . . . , an

Output: The sequence in the increasing order

Algorithm:

TrungDT (FUHN) MAD101 Chapter 3 12 / 45

Bubble Sort

Input: A sequence of integers a1 , a2 , . . . , an

Output: The sequence in the increasing order

Algorithm:

1 Successively comparing two consecutive elements of the list to push

the largest element to the bottom of the list.

TrungDT (FUHN) MAD101 Chapter 3 12 / 45

Bubble Sort

Input: A sequence of integers a1 , a2 , . . . , an

Output: The sequence in the increasing order

Algorithm:

1 Successively comparing two consecutive elements of the list to push

the largest element to the bottom of the list.
2 Repeat the above step for the first n − 1 elements of the list.

TrungDT (FUHN) MAD101 Chapter 3 12 / 45

Bubble Sort

Input: A sequence of integers a1 , a2 , . . . , an

Output: The sequence in the increasing order

Algorithm:

1 Successively comparing two consecutive elements of the list to push

the largest element to the bottom of the list.
2 Repeat the above step for the first n − 1 elements of the list.

TrungDT (FUHN) MAD101 Chapter 3 12 / 45

Bubble Sort

Input: A sequence of integers a1 , a2 , . . . , an

Output: The sequence in the increasing order

Algorithm:

1 Successively comparing two consecutive elements of the list to push

the largest element to the bottom of the list.
2 Repeat the above step for the first n − 1 elements of the list.

TrungDT (FUHN) MAD101 Chapter 3 12 / 45

TrungDT (FUHN) MAD101 Chapter 3 13 / 45
Example.

TrungDT (FUHN) MAD101 Chapter 3 13 / 45

Example. Run the Bubble sort algorithm for the list 3, 2, 4, 1, 5.

TrungDT (FUHN) MAD101 Chapter 3 13 / 45

Example. Run the Bubble sort algorithm for the list 3, 2, 4, 1, 5.

TrungDT (FUHN) MAD101 Chapter 3 13 / 45

Example. Run the Bubble sort algorithm for the list 3, 2, 4, 1, 5.

Procedure BubbleSort(a1 , a2 , . . . , an : integers)

TrungDT (FUHN) MAD101 Chapter 3 13 / 45

Example. Run the Bubble sort algorithm for the list 3, 2, 4, 1, 5.

Procedure BubbleSort(a1 , a2 , . . . , an : integers)

for i := 1 to n − 1

TrungDT (FUHN) MAD101 Chapter 3 13 / 45

Example. Run the Bubble sort algorithm for the list 3, 2, 4, 1, 5.

Procedure BubbleSort(a1 , a2 , . . . , an : integers)

for i := 1 to n − 1
for j := 1 to n − i

TrungDT (FUHN) MAD101 Chapter 3 13 / 45

Example. Run the Bubble sort algorithm for the list 3, 2, 4, 1, 5.

Procedure BubbleSort(a1 , a2 , . . . , an : integers)

for i := 1 to n − 1
for j := 1 to n − i
if aj > aj+1 then swap(aj , aj+1 )

TrungDT (FUHN) MAD101 Chapter 3 13 / 45

TrungDT (FUHN) MAD101 Chapter 3 14 / 45
TrungDT (FUHN) MAD101 Chapter 3 14 / 45
Insertion Sort

TrungDT (FUHN) MAD101 Chapter 3 15 / 45

Insertion Sort

Input: Sequence of integers a1 , a2 , . . . , an

TrungDT (FUHN) MAD101 Chapter 3 15 / 45

Insertion Sort

Input: Sequence of integers a1 , a2 , . . . , an

Output: The sequence in the increasing order

TrungDT (FUHN) MAD101 Chapter 3 15 / 45

Insertion Sort

Input: Sequence of integers a1 , a2 , . . . , an

Output: The sequence in the increasing order

Algorithm:

TrungDT (FUHN) MAD101 Chapter 3 15 / 45

Insertion Sort

Input: Sequence of integers a1 , a2 , . . . , an

Output: The sequence in the increasing order

Algorithm:

1 Sort the first two elements of the list

TrungDT (FUHN) MAD101 Chapter 3 15 / 45

Insertion Sort

Input: Sequence of integers a1 , a2 , . . . , an

Output: The sequence in the increasing order

Algorithm:

1 Sort the first two elements of the list

2 Insert the third element to the list of the first two elements to get a
list of 3 elements of increasing order.

TrungDT (FUHN) MAD101 Chapter 3 15 / 45

Insertion Sort

Input: Sequence of integers a1 , a2 , . . . , an

Output: The sequence in the increasing order

Algorithm:

1 Sort the first two elements of the list

2 Insert the third element to the list of the first two elements to get a
list of 3 elements of increasing order.
3 Insert the fourth element to the list of the first three elements to get
a list of 4 elements of increasing order.

TrungDT (FUHN) MAD101 Chapter 3 15 / 45

Insertion Sort

Input: Sequence of integers a1 , a2 , . . . , an

Output: The sequence in the increasing order

Algorithm:

1 Sort the first two elements of the list

2 Insert the third element to the list of the first two elements to get a
list of 3 elements of increasing order.
3 Insert the fourth element to the list of the first three elements to get
a list of 4 elements of increasing order.

TrungDT (FUHN) MAD101 Chapter 3 15 / 45

Insertion Sort

Input: Sequence of integers a1 , a2 , . . . , an

Output: The sequence in the increasing order

Algorithm:

1 Sort the first two elements of the list

2 Insert the third element to the list of the first two elements to get a
list of 3 elements of increasing order.
3 Insert the fourth element to the list of the first three elements to get
a list of 4 elements of increasing order.
...
n Insert the nth element to the list of the first n − 1 elements to get a
list of increasing order.

TrungDT (FUHN) MAD101 Chapter 3 15 / 45

Insertion Sort

Input: Sequence of integers a1 , a2 , . . . , an

Output: The sequence in the increasing order

Algorithm:

1 Sort the first two elements of the list

2 Insert the third element to the list of the first two elements to get a
list of 3 elements of increasing order.
3 Insert the fourth element to the list of the first three elements to get
a list of 4 elements of increasing order.
...
n Insert the nth element to the list of the first n − 1 elements to get a
list of increasing order.

TrungDT (FUHN) MAD101 Chapter 3 15 / 45

TrungDT (FUHN) MAD101 Chapter 3 16 / 45
Procedure InsertionSort(a1 , a2 , . . . , an : integers)

TrungDT (FUHN) MAD101 Chapter 3 16 / 45

Procedure InsertionSort(a1 , a2 , . . . , an : integers)
for j := 2 to n

TrungDT (FUHN) MAD101 Chapter 3 16 / 45

Procedure InsertionSort(a1 , a2 , . . . , an : integers)
for j := 2 to n
begin

TrungDT (FUHN) MAD101 Chapter 3 16 / 45

Procedure InsertionSort(a1 , a2 , . . . , an : integers)
for j := 2 to n
begin
i := 1

TrungDT (FUHN) MAD101 Chapter 3 16 / 45

Procedure InsertionSort(a1 , a2 , . . . , an : integers)
for j := 2 to n
begin
i := 1
while aj > ai

TrungDT (FUHN) MAD101 Chapter 3 16 / 45

Procedure InsertionSort(a1 , a2 , . . . , an : integers)
for j := 2 to n
begin
i := 1
while aj > ai
i := i + 1

TrungDT (FUHN) MAD101 Chapter 3 16 / 45

Procedure InsertionSort(a1 , a2 , . . . , an : integers)
for j := 2 to n
begin
i := 1
while aj > ai
i := i + 1
m := aj

TrungDT (FUHN) MAD101 Chapter 3 16 / 45

Procedure InsertionSort(a1 , a2 , . . . , an : integers)
for j := 2 to n
begin
i := 1
while aj > ai
i := i + 1
m := aj
k := j

TrungDT (FUHN) MAD101 Chapter 3 16 / 45

Procedure InsertionSort(a1 , a2 , . . . , an : integers)
for j := 2 to n
begin
i := 1
while aj > ai
i := i + 1
m := aj
k := j
while k > i

TrungDT (FUHN) MAD101 Chapter 3 16 / 45

Procedure InsertionSort(a1 , a2 , . . . , an : integers)
for j := 2 to n
begin
i := 1
while aj > ai
i := i + 1
m := aj
k := j
while k > i
ak := ak−1

TrungDT (FUHN) MAD101 Chapter 3 16 / 45

Procedure InsertionSort(a1 , a2 , . . . , an : integers)
for j := 2 to n
begin
i := 1
while aj > ai
i := i + 1
m := aj
k := j
while k > i
ak := ak−1
k := k − 1

TrungDT (FUHN) MAD101 Chapter 3 16 / 45

Procedure InsertionSort(a1 , a2 , . . . , an : integers)
for j := 2 to n
begin
i := 1
while aj > ai
i := i + 1
m := aj
k := j
while k > i
ak := ak−1
k := k − 1
ai := m

TrungDT (FUHN) MAD101 Chapter 3 16 / 45

Procedure InsertionSort(a1 , a2 , . . . , an : integers)
for j := 2 to n
begin
i := 1
while aj > ai
i := i + 1
m := aj
k := j
while k > i
ak := ak−1
k := k − 1
ai := m
end

TrungDT (FUHN) MAD101 Chapter 3 16 / 45

Greedy Change-Making Algorithm

TrungDT (FUHN) MAD101 Chapter 3 17 / 45

Greedy Change-Making Algorithm

Input: n cents

TrungDT (FUHN) MAD101 Chapter 3 17 / 45

Greedy Change-Making Algorithm

Input: n cents
Output: The least number of coins using quarters (= 25 cents),
dimes (= 10 cents), nickles (= 5 cents) and pennies ( = 1 cent).

TrungDT (FUHN) MAD101 Chapter 3 17 / 45

Greedy Change-Making Algorithm

Input: n cents
Output: The least number of coins using quarters (= 25 cents),
dimes (= 10 cents), nickles (= 5 cents) and pennies ( = 1 cent).

TrungDT (FUHN) MAD101 Chapter 3 17 / 45

Greedy Change-Making Algorithm

Input: n cents
Output: The least number of coins using quarters (= 25 cents),
dimes (= 10 cents), nickles (= 5 cents) and pennies ( = 1 cent).

Algorithm: Read textbook!

TrungDT (FUHN) MAD101 Chapter 3 17 / 45

3.2 The Growth of Functions

TrungDT (FUHN) MAD101 Chapter 3 18 / 45

3.2 The Growth of Functions
In calculus, we learned following basic functions, listed in the increasing
order of their complexity:

TrungDT (FUHN) MAD101 Chapter 3 18 / 45

3.2 The Growth of Functions
In calculus, we learned following basic functions, listed in the increasing
order of their complexity:

log n, nk , an , n!,

TrungDT (FUHN) MAD101 Chapter 3 18 / 45

3.2 The Growth of Functions
In calculus, we learned following basic functions, listed in the increasing
order of their complexity:

log n, nk , an , n!,

where k > 0 and a > 1.

TrungDT (FUHN) MAD101 Chapter 3 18 / 45

3.2 The Growth of Functions
In calculus, we learned following basic functions, listed in the increasing
order of their complexity:

log n, nk , an , n!,

where k > 0 and a > 1.

That means:

TrungDT (FUHN) MAD101 Chapter 3 18 / 45

3.2 The Growth of Functions
In calculus, we learned following basic functions, listed in the increasing
order of their complexity:

log n, nk , an , n!,

where k > 0 and a > 1.

That means:
nk
lim =∞
n→∞ log n

TrungDT (FUHN) MAD101 Chapter 3 18 / 45

3.2 The Growth of Functions
In calculus, we learned following basic functions, listed in the increasing
order of their complexity:

log n, nk , an , n!,

where k > 0 and a > 1.

That means:
nk an
lim =∞ lim =∞
n→∞ log n n→∞ nk

TrungDT (FUHN) MAD101 Chapter 3 18 / 45

3.2 The Growth of Functions
In calculus, we learned following basic functions, listed in the increasing
order of their complexity:

log n, nk , an , n!,

where k > 0 and a > 1.

That means:
nk an n!
lim =∞ lim =∞ lim =∞
n→∞ log n n→∞ nk n→∞ an

TrungDT (FUHN) MAD101 Chapter 3 18 / 45

3.2 The Growth of Functions
In calculus, we learned following basic functions, listed in the increasing
order of their complexity:

log n, nk , an , n!,

where k > 0 and a > 1.

That means:
nk an n!
lim =∞ lim =∞ lim =∞
n→∞ log n n→∞ nk n→∞ an

Question.

TrungDT (FUHN) MAD101 Chapter 3 18 / 45

3.2 The Growth of Functions
In calculus, we learned following basic functions, listed in the increasing
order of their complexity:

log n, nk , an , n!,

where k > 0 and a > 1.

That means:
nk an n!
lim =∞ lim =∞ lim =∞
n→∞ log n n→∞ nk n→∞ an

Question. Estimate the complexity (the growth) of functions like:

TrungDT (FUHN) MAD101 Chapter 3 18 / 45

3.2 The Growth of Functions
In calculus, we learned following basic functions, listed in the increasing
order of their complexity:

log n, nk , an , n!,

where k > 0 and a > 1.

That means:
nk an n!
lim =∞ lim =∞ lim =∞
n→∞ log n n→∞ nk n→∞ an

Question. Estimate the complexity (the growth) of functions like:

(n + 2)(n log n + n!)

f (n) =
3n + (log n)2

TrungDT (FUHN) MAD101 Chapter 3 18 / 45

3.2 The Growth of Functions
In calculus, we learned following basic functions, listed in the increasing
order of their complexity:

log n, nk , an , n!,

where k > 0 and a > 1.

That means:
nk an n!
lim =∞ lim =∞ lim =∞
n→∞ log n n→∞ nk n→∞ an

Question. Estimate the complexity (the growth) of functions like:

(n + 2)(n log n + n!)

f (n) =
3n + (log n)2

via simpler functions.

TrungDT (FUHN) MAD101 Chapter 3 18 / 45
3.2 The Growth of Functions
In calculus, we learned following basic functions, listed in the increasing
order of their complexity:

log n, nk , an , n!,

where k > 0 and a > 1.

That means:
nk an n!
lim =∞ lim =∞ lim =∞
n→∞ log n n→∞ nk n→∞ an

Question. Estimate the complexity (the growth) of functions like:

(n + 2)(n log n + n!)

f (n) =
3n + (log n)2

via simpler functions.

TrungDT (FUHN) MAD101 Chapter 3 18 / 45
Big-O

TrungDT (FUHN) MAD101 Chapter 3 19 / 45

Big-O

TrungDT (FUHN) MAD101 Chapter 3 19 / 45

Big-O

The function f (x) is called big-O of g (x), write f (x) is O(g (x)), if there
is a constant C such that

TrungDT (FUHN) MAD101 Chapter 3 19 / 45

Big-O

The function f (x) is called big-O of g (x), write f (x) is O(g (x)), if there
is a constant C such that

|f (x)| ≤ C |g (x)|

TrungDT (FUHN) MAD101 Chapter 3 19 / 45

Big-O

The function f (x) is called big-O of g (x), write f (x) is O(g (x)), if there
is a constant C such that

|f (x)| ≤ C |g (x)|

for all x large enough, (meaning, it is true for all x > k for some k).

TrungDT (FUHN) MAD101 Chapter 3 19 / 45

Big-O

The function f (x) is called big-O of g (x), write f (x) is O(g (x)), if there
is a constant C such that

|f (x)| ≤ C |g (x)|

for all x large enough, (meaning, it is true for all x > k for some k).

Example.

TrungDT (FUHN) MAD101 Chapter 3 19 / 45

Big-O

The function f (x) is called big-O of g (x), write f (x) is O(g (x)), if there
is a constant C such that

|f (x)| ≤ C |g (x)|

for all x large enough, (meaning, it is true for all x > k for some k).

Example.

(a) Show that x 5 − 2x 2 + 7 is O(x 5 ).

TrungDT (FUHN) MAD101 Chapter 3 19 / 45

Big-O

The function f (x) is called big-O of g (x), write f (x) is O(g (x)), if there
is a constant C such that

|f (x)| ≤ C |g (x)|

for all x large enough, (meaning, it is true for all x > k for some k).

Example.

(a) Show that x 5 − 2x 2 + 7 is O(x 5 ).

(b) Show that x 5 − 2x 2 + 7 is not O(x 4 ).

TrungDT (FUHN) MAD101 Chapter 3 19 / 45

Theorem 1

TrungDT (FUHN) MAD101 Chapter 3 20 / 45

Theorem 1
Let f (x) be a polynomial of degree n. Then f (x) is O(x n ).

TrungDT (FUHN) MAD101 Chapter 3 20 / 45

Theorem 1
Let f (x) be a polynomial of degree n. Then f (x) is O(x n ).
This estimate is the best possible, meaning f (x) is not big-O of any power
of x that is less than n.

TrungDT (FUHN) MAD101 Chapter 3 20 / 45

Theorem 1
Let f (x) be a polynomial of degree n. Then f (x) is O(x n ).
This estimate is the best possible, meaning f (x) is not big-O of any power
of x that is less than n.

Theorem 2

TrungDT (FUHN) MAD101 Chapter 3 20 / 45

Theorem 1
Let f (x) be a polynomial of degree n. Then f (x) is O(x n ).
This estimate is the best possible, meaning f (x) is not big-O of any power
of x that is less than n.

Theorem 2
Assume that f1 (x) is O(g1 (x)) and f2 (x) is O(g2 (x)). Then:

TrungDT (FUHN) MAD101 Chapter 3 20 / 45

Theorem 1
Let f (x) be a polynomial of degree n. Then f (x) is O(x n ).
This estimate is the best possible, meaning f (x) is not big-O of any power
of x that is less than n.

Theorem 2
Assume that f1 (x) is O(g1 (x)) and f2 (x) is O(g2 (x)). Then:
f1 (x) + f2 (x) is big-O of the maximum of g1 (x) and g2 (x).

TrungDT (FUHN) MAD101 Chapter 3 20 / 45

Theorem 1
Let f (x) be a polynomial of degree n. Then f (x) is O(x n ).
This estimate is the best possible, meaning f (x) is not big-O of any power
of x that is less than n.

Theorem 2
Assume that f1 (x) is O(g1 (x)) and f2 (x) is O(g2 (x)). Then:
f1 (x) + f2 (x) is big-O of the maximum of g1 (x) and g2 (x).
f1 (x)f2 (x) is big-O of g1 (x)g2 (x).

TrungDT (FUHN) MAD101 Chapter 3 20 / 45

Theorem 1
Let f (x) be a polynomial of degree n. Then f (x) is O(x n ).
This estimate is the best possible, meaning f (x) is not big-O of any power
of x that is less than n.

Theorem 2
Assume that f1 (x) is O(g1 (x)) and f2 (x) is O(g2 (x)). Then:
f1 (x) + f2 (x) is big-O of the maximum of g1 (x) and g2 (x).
f1 (x)f2 (x) is big-O of g1 (x)g2 (x).

TrungDT (FUHN) MAD101 Chapter 3 20 / 45

TrungDT (FUHN) MAD101 Chapter 3 21 / 45
Example 1. Give a big-O estimate that is simple and effective for each of
the functions:

TrungDT (FUHN) MAD101 Chapter 3 21 / 45

Example 1. Give a big-O estimate that is simple and effective for each of
the functions:

(a) n2 log n + 3n2 + 5

TrungDT (FUHN) MAD101 Chapter 3 21 / 45

Example 1. Give a big-O estimate that is simple and effective for each of
the functions:

(a) n2 log n + 3n2 + 5

(b) (n3 + 2n )(n! + n2 5n )

TrungDT (FUHN) MAD101 Chapter 3 21 / 45

Example 1. Give a big-O estimate that is simple and effective for each of
the functions:

(a) n2 log n + 3n2 + 5

(b) (n3 + 2n )(n! + n2 5n )

Example 2. Find the smallest integer n such that:

TrungDT (FUHN) MAD101 Chapter 3 21 / 45

Example 1. Give a big-O estimate that is simple and effective for each of
the functions:

(a) n2 log n + 3n2 + 5

(b) (n3 + 2n )(n! + n2 5n )

Example 2. Find the smallest integer n such that:

(a) x 3 + x 5 log x is O(x n )

TrungDT (FUHN) MAD101 Chapter 3 21 / 45

Example 1. Give a big-O estimate that is simple and effective for each of
the functions:

(a) n2 log n + 3n2 + 5

(b) (n3 + 2n )(n! + n2 5n )

Example 2. Find the smallest integer n such that:

(a) x 3 + x 5 log x is O(x n )

(b) x 5 + x 3 (log x)4 is O(x n )

TrungDT (FUHN) MAD101 Chapter 3 21 / 45

Big-theta

TrungDT (FUHN) MAD101 Chapter 3 22 / 45

Big-theta

Big-O estimates only give upper-bounds; to give sharper bounds we use

big-theta notation.

TrungDT (FUHN) MAD101 Chapter 3 22 / 45

Big-theta

Big-O estimates only give upper-bounds; to give sharper bounds we use

big-theta notation.

The function f (x) is called big-theta of g (x), write: f (x) is Θ(g (x)), if
f (x) is O(g (x)) and g (x) is O(f (x)).

TrungDT (FUHN) MAD101 Chapter 3 22 / 45

Big-theta

Big-O estimates only give upper-bounds; to give sharper bounds we use

big-theta notation.

The function f (x) is called big-theta of g (x), write: f (x) is Θ(g (x)), if
f (x) is O(g (x)) and g (x) is O(f (x)).
In other words,

TrungDT (FUHN) MAD101 Chapter 3 22 / 45

Big-theta

Big-O estimates only give upper-bounds; to give sharper bounds we use

big-theta notation.

The function f (x) is called big-theta of g (x), write: f (x) is Θ(g (x)), if
f (x) is O(g (x)) and g (x) is O(f (x)).
In other words, f (x) is Θ(g (x)) if there are constants C1 , C2 > 0 such that

TrungDT (FUHN) MAD101 Chapter 3 22 / 45

Big-theta

Big-O estimates only give upper-bounds; to give sharper bounds we use

big-theta notation.

The function f (x) is called big-theta of g (x), write: f (x) is Θ(g (x)), if
f (x) is O(g (x)) and g (x) is O(f (x)).
In other words, f (x) is Θ(g (x)) if there are constants C1 , C2 > 0 such that

C1 |g (x)| ≤ |f (x)| ≤ C2 |g (x)|

TrungDT (FUHN) MAD101 Chapter 3 22 / 45

Big-theta

Big-O estimates only give upper-bounds; to give sharper bounds we use

big-theta notation.

The function f (x) is called big-theta of g (x), write: f (x) is Θ(g (x)), if
f (x) is O(g (x)) and g (x) is O(f (x)).
In other words, f (x) is Θ(g (x)) if there are constants C1 , C2 > 0 such that

C1 |g (x)| ≤ |f (x)| ≤ C2 |g (x)|

for all x large enough.

TrungDT (FUHN) MAD101 Chapter 3 22 / 45

Big-theta

Big-O estimates only give upper-bounds; to give sharper bounds we use

big-theta notation.

The function f (x) is called big-theta of g (x), write: f (x) is Θ(g (x)), if
f (x) is O(g (x)) and g (x) is O(f (x)).
In other words, f (x) is Θ(g (x)) if there are constants C1 , C2 > 0 such that

C1 |g (x)| ≤ |f (x)| ≤ C2 |g (x)|

for all x large enough.

TrungDT (FUHN) MAD101 Chapter 3 22 / 45

Big-theta

Big-O estimates only give upper-bounds; to give sharper bounds we use

big-theta notation.

The function f (x) is called big-theta of g (x), write: f (x) is Θ(g (x)), if
f (x) is O(g (x)) and g (x) is O(f (x)).
In other words, f (x) is Θ(g (x)) if there are constants C1 , C2 > 0 such that

C1 |g (x)| ≤ |f (x)| ≤ C2 |g (x)|

for all x large enough.

Note: is f (x) is Θ(g (x)) and g (x) is also Θ(f (x)).

TrungDT (FUHN) MAD101 Chapter 3 22 / 45

Big-theta

Big-O estimates only give upper-bounds; to give sharper bounds we use

big-theta notation.

The function f (x) is called big-theta of g (x), write: f (x) is Θ(g (x)), if
f (x) is O(g (x)) and g (x) is O(f (x)).
In other words, f (x) is Θ(g (x)) if there are constants C1 , C2 > 0 such that

C1 |g (x)| ≤ |f (x)| ≤ C2 |g (x)|

for all x large enough.

Note: is f (x) is Θ(g (x)) and g (x) is also Θ(f (x)). Therefore, if f (x) is
Θ(g (x)) we say f (x) is of order g (x).

TrungDT (FUHN) MAD101 Chapter 3 22 / 45

TrungDT (FUHN) MAD101 Chapter 3 23 / 45
Example.

TrungDT (FUHN) MAD101 Chapter 3 23 / 45

Example.

(a) Show that f (x) = 2x 3 + x 2 + 3 is Θ(x 3 ).

TrungDT (FUHN) MAD101 Chapter 3 23 / 45

Example.

(a) Show that f (x) = 2x 3 + x 2 + 3 is Θ(x 3 ).

(b) Is the function f (x) = x 2 log x + 3x + 1 big-theta of x 3 ?

TrungDT (FUHN) MAD101 Chapter 3 23 / 45

Example.

(a) Show that f (x) = 2x 3 + x 2 + 3 is Θ(x 3 ).

(b) Is the function f (x) = x 2 log x + 3x + 1 big-theta of x 3 ?
(c) Show that f (x) = bx/2c is Θ(x)

TrungDT (FUHN) MAD101 Chapter 3 23 / 45

3.3 Complexity of Algorithms

TrungDT (FUHN) MAD101 Chapter 3 24 / 45

3.3 Complexity of Algorithms

Space complexity:

TrungDT (FUHN) MAD101 Chapter 3 24 / 45

3.3 Complexity of Algorithms

Space complexity: Computer memory required to run the algorithm

TrungDT (FUHN) MAD101 Chapter 3 24 / 45

3.3 Complexity of Algorithms

Space complexity: Computer memory required to run the algorithm

Time complexity:

TrungDT (FUHN) MAD101 Chapter 3 24 / 45

3.3 Complexity of Algorithms

Space complexity: Computer memory required to run the algorithm

Time complexity: Time required to run the algorithm.

TrungDT (FUHN) MAD101 Chapter 3 24 / 45

3.3 Complexity of Algorithms

Space complexity: Computer memory required to run the algorithm

Time complexity: Time required to run the algorithm. Time
complexity can be expressed in terms of the number of operations
used by the algorithm.

TrungDT (FUHN) MAD101 Chapter 3 24 / 45

3.3 Complexity of Algorithms

Space complexity: Computer memory required to run the algorithm

Time complexity: Time required to run the algorithm. Time
complexity can be expressed in terms of the number of operations
used by the algorithm. Those operations can be comparisons or basic
arithmetic operations.

TrungDT (FUHN) MAD101 Chapter 3 24 / 45

3.3 Complexity of Algorithms

Space complexity: Computer memory required to run the algorithm

Time complexity: Time required to run the algorithm. Time
complexity can be expressed in terms of the number of operations
used by the algorithm. Those operations can be comparisons or basic
arithmetic operations.

In this lecture we analyze time complexity of some algorithms studied in

previous sections.

TrungDT (FUHN) MAD101 Chapter 3 24 / 45

Complexity of Algorithm of Finding Maximum Element

TrungDT (FUHN) MAD101 Chapter 3 25 / 45

Complexity of Algorithm of Finding Maximum Element

TrungDT (FUHN) MAD101 Chapter 3 25 / 45

Complexity of Algorithm of Finding Maximum Element

Number of loops: n − 1

TrungDT (FUHN) MAD101 Chapter 3 25 / 45

Complexity of Algorithm of Finding Maximum Element

Number of loops: n − 1
Number of comparisons in
each loop: 2

TrungDT (FUHN) MAD101 Chapter 3 25 / 45

Complexity of Algorithm of Finding Maximum Element

Number of loops: n − 1
Number of comparisons in
each loop: 2
Number of comparisons to
exit the loop: 1

TrungDT (FUHN) MAD101 Chapter 3 25 / 45

Complexity of Algorithm of Finding Maximum Element

Number of loops: n − 1
Number of comparisons in
each loop: 2
Number of comparisons to
exit the loop: 1
Total number of comparisons:
2(n − 1) + 1 = 2n − 1 = O(n)

TrungDT (FUHN) MAD101 Chapter 3 25 / 45

Complexity of Linear Search Algorithm

TrungDT (FUHN) MAD101 Chapter 3 26 / 45

Complexity of Linear Search Algorithm

TrungDT (FUHN) MAD101 Chapter 3 26 / 45

Complexity of Linear Search Algorithm

If x do not appear in the list:

TrungDT (FUHN) MAD101 Chapter 3 26 / 45

Complexity of Linear Search Algorithm

If x do not appear in the list:

n loops

TrungDT (FUHN) MAD101 Chapter 3 26 / 45

Complexity of Linear Search Algorithm

If x do not appear in the list:

n loops
2 comparisons in each loop

TrungDT (FUHN) MAD101 Chapter 3 26 / 45

Complexity of Linear Search Algorithm

If x do not appear in the list:

n loops
2 comparisons in each loop
1 comparison to exit the loop

TrungDT (FUHN) MAD101 Chapter 3 26 / 45

Complexity of Linear Search Algorithm

If x do not appear in the list:

n loops
2 comparisons in each loop
1 comparison to exit the loop
1 comparison outside the loop

TrungDT (FUHN) MAD101 Chapter 3 26 / 45

Complexity of Linear Search Algorithm

If x do not appear in the list:

n loops
2 comparisons in each loop
1 comparison to exit the loop
1 comparison outside the loop
Total number of comparisons:
2n + 1 + 1 = 2n + 2 = O(n)

TrungDT (FUHN) MAD101 Chapter 3 26 / 45

Complexity of Linear Search Algorithm

TrungDT (FUHN) MAD101 Chapter 3 27 / 45

Complexity of Linear Search Algorithm

TrungDT (FUHN) MAD101 Chapter 3 27 / 45

Complexity of Linear Search Algorithm

If x is at the ith location:

TrungDT (FUHN) MAD101 Chapter 3 27 / 45

Complexity of Linear Search Algorithm

If x is at the ith location:

i − 1 loops

TrungDT (FUHN) MAD101 Chapter 3 27 / 45

Complexity of Linear Search Algorithm

If x is at the ith location:

i − 1 loops
2 comparisons in each loop

TrungDT (FUHN) MAD101 Chapter 3 27 / 45

Complexity of Linear Search Algorithm

If x is at the ith location:

i − 1 loops
2 comparisons in each loop
2 comparisons to exit the loop

TrungDT (FUHN) MAD101 Chapter 3 27 / 45

Complexity of Linear Search Algorithm

If x is at the ith location:

i − 1 loops
2 comparisons in each loop
2 comparisons to exit the loop
1 outside the loop

TrungDT (FUHN) MAD101 Chapter 3 27 / 45

Complexity of Linear Search Algorithm

If x is at the ith location:

i − 1 loops
2 comparisons in each loop
2 comparisons to exit the loop
1 outside the loop
Total number of comparisons:
2(i − 1) + 2 + 1 = 2i + 1

TrungDT (FUHN) MAD101 Chapter 3 27 / 45

Complexity of Binary Search Algorithm

TrungDT (FUHN) MAD101 Chapter 3 28 / 45

Complexity of Binary Search Algorithm

TrungDT (FUHN) MAD101 Chapter 3 28 / 45

Complexity of Binary Search Algorithm

Assume n = 2k

TrungDT (FUHN) MAD101 Chapter 3 28 / 45

Complexity of Binary Search Algorithm

Assume n = 2k

k loops

TrungDT (FUHN) MAD101 Chapter 3 28 / 45

Complexity of Binary Search Algorithm

Assume n = 2k

k loops
2 comparisons in each
loop

TrungDT (FUHN) MAD101 Chapter 3 28 / 45

Complexity of Binary Search Algorithm

Assume n = 2k

k loops
2 comparisons in each
loop
1 comparison to exit
the loop

TrungDT (FUHN) MAD101 Chapter 3 28 / 45

Complexity of Binary Search Algorithm

Assume n = 2k

k loops
2 comparisons in each
loop
1 comparison to exit
the loop
1 comparison outside
the loop

TrungDT (FUHN) MAD101 Chapter 3 28 / 45

Complexity of Binary Search Algorithm

Assume n = 2k

k loops
2 comparisons in each
loop
1 comparison to exit
the loop
1 comparison outside
the loop
Total number of
comparisons:
2k + 1 + 1 = 2k + 2
= 2dlog ne + 2
= O(log n)

TrungDT (FUHN) MAD101 Chapter 3 28 / 45

TrungDT (FUHN) MAD101 Chapter 3 29 / 45
Exercise.

TrungDT (FUHN) MAD101 Chapter 3 29 / 45

Exercise.

Analyze the complexity of Bubble sort and Insertion sort algorithms.

TrungDT (FUHN) MAD101 Chapter 3 29 / 45

TrungDT (FUHN) MAD101 Chapter 3 30 / 45
 Commonly used terminologies
for the complexity of algorithms
Complexity Terminology
O(1) Constant complexity
O(log n) Logarithmic complexity
O(n) Linear complexity
O(n log n) n log n complexity
k
O(n ) Polynomial complexity
O(b n ), b > 1 Exponential complexity
O(n!) Factorial complexity

TrungDT (FUHN) MAD101 Chapter 3 30 / 45

3.4 The Integers and Division

TrungDT (FUHN) MAD101 Chapter 3 31 / 45

3.4 The Integers and Division
Let a, b be integers with a 6= 0. We say the integer a divides b if there is
an integer m such that b = am.

TrungDT (FUHN) MAD101 Chapter 3 31 / 45

3.4 The Integers and Division
Let a, b be integers with a 6= 0. We say the integer a divides b if there is
an integer m such that b = am.

TrungDT (FUHN) MAD101 Chapter 3 31 / 45

3.4 The Integers and Division
Let a, b be integers with a 6= 0. We say the integer a divides b if there is
an integer m such that b = am.

If a divides b we also write:

TrungDT (FUHN) MAD101 Chapter 3 31 / 45

3.4 The Integers and Division
Let a, b be integers with a 6= 0. We say the integer a divides b if there is
an integer m such that b = am.

If a divides b we also write:

b is divisible by a

TrungDT (FUHN) MAD101 Chapter 3 31 / 45

3.4 The Integers and Division
Let a, b be integers with a 6= 0. We say the integer a divides b if there is
an integer m such that b = am.

If a divides b we also write:

b is divisible by a
b is a multiple of a

TrungDT (FUHN) MAD101 Chapter 3 31 / 45

3.4 The Integers and Division
Let a, b be integers with a 6= 0. We say the integer a divides b if there is
an integer m such that b = am.

If a divides b we also write:

b is divisible by a
b is a multiple of a
a is a factor of b

TrungDT (FUHN) MAD101 Chapter 3 31 / 45

3.4 The Integers and Division
Let a, b be integers with a 6= 0. We say the integer a divides b if there is
an integer m such that b = am.

If a divides b we also write:

b is divisible by a
b is a multiple of a
a is a factor of b
a|b

TrungDT (FUHN) MAD101 Chapter 3 31 / 45

3.4 The Integers and Division
Let a, b be integers with a 6= 0. We say the integer a divides b if there is
an integer m such that b = am.

If a divides b we also write:

b is divisible by a
b is a multiple of a
a is a factor of b
a|b

Theorem

TrungDT (FUHN) MAD101 Chapter 3 31 / 45

3.4 The Integers and Division
Let a, b be integers with a 6= 0. We say the integer a divides b if there is
an integer m such that b = am.

If a divides b we also write:

b is divisible by a
b is a multiple of a
a is a factor of b
a|b

Theorem
Let a, b, c be integers. Then:

TrungDT (FUHN) MAD101 Chapter 3 31 / 45

3.4 The Integers and Division
Let a, b be integers with a 6= 0. We say the integer a divides b if there is
an integer m such that b = am.

If a divides b we also write:

b is divisible by a
b is a multiple of a
a is a factor of b
a|b

Theorem
Let a, b, c be integers. Then:
If a | b and a | c then a | (b + c)

TrungDT (FUHN) MAD101 Chapter 3 31 / 45

3.4 The Integers and Division
Let a, b be integers with a 6= 0. We say the integer a divides b if there is
an integer m such that b = am.

If a divides b we also write:

b is divisible by a
b is a multiple of a
a is a factor of b
a|b

Theorem
Let a, b, c be integers. Then:
If a | b and a | c then a | (b + c)
If a | b then a | bc for all c

TrungDT (FUHN) MAD101 Chapter 3 31 / 45

3.4 The Integers and Division
Let a, b be integers with a 6= 0. We say the integer a divides b if there is
an integer m such that b = am.

If a divides b we also write:

b is divisible by a
b is a multiple of a
a is a factor of b
a|b

Theorem
Let a, b, c be integers. Then:
If a | b and a | c then a | (b + c)
If a | b then a | bc for all c
If a | b and b | c then a | c
TrungDT (FUHN) MAD101 Chapter 3 31 / 45
The Division Algorithm

TrungDT (FUHN) MAD101 Chapter 3 32 / 45

The Division Algorithm

Let a be an integer and d a positive integer.

TrungDT (FUHN) MAD101 Chapter 3 32 / 45

The Division Algorithm

Let a be an integer and d a positive integer. Then there are unique

integers q and r with 0 ≤ r < d such that a = dq + r .

TrungDT (FUHN) MAD101 Chapter 3 32 / 45

The Division Algorithm

Let a be an integer and d a positive integer. Then there are unique

integers q and r with 0 ≤ r < d such that a = dq + r .
In this division algorithm, a is called the dividend, d is the divisor, q is
the quotient and r is the remainder.

TrungDT (FUHN) MAD101 Chapter 3 32 / 45

The Division Algorithm

Let a be an integer and d a positive integer. Then there are unique

integers q and r with 0 ≤ r < d such that a = dq + r .
In this division algorithm, a is called the dividend, d is the divisor, q is
the quotient and r is the remainder. We write

q = a div d, r = a mod d

TrungDT (FUHN) MAD101 Chapter 3 32 / 45

The Division Algorithm

Let a be an integer and d a positive integer. Then there are unique

integers q and r with 0 ≤ r < d such that a = dq + r .
In this division algorithm, a is called the dividend, d is the divisor, q is
the quotient and r is the remainder. We write

q = a div d, r = a mod d

Example. Find the remainder and the quotient of the division:

TrungDT (FUHN) MAD101 Chapter 3 32 / 45

The Division Algorithm

Let a be an integer and d a positive integer. Then there are unique

integers q and r with 0 ≤ r < d such that a = dq + r .
In this division algorithm, a is called the dividend, d is the divisor, q is
the quotient and r is the remainder. We write

q = a div d, r = a mod d

Example. Find the remainder and the quotient of the division:

(a) -23 is divided by 7

TrungDT (FUHN) MAD101 Chapter 3 32 / 45

The Division Algorithm

Let a be an integer and d a positive integer. Then there are unique

integers q and r with 0 ≤ r < d such that a = dq + r .
In this division algorithm, a is called the dividend, d is the divisor, q is
the quotient and r is the remainder. We write

q = a div d, r = a mod d

Example. Find the remainder and the quotient of the division:

(a) -23 is divided by 7

(b) -125 is divided by 11

TrungDT (FUHN) MAD101 Chapter 3 32 / 45

Modular Arithmetic

TrungDT (FUHN) MAD101 Chapter 3 33 / 45

Modular Arithmetic

Let a, b be integers and m a positive integer. We say a is congruent to b

modulo m is they have the same remainders when being divided by d. We
use notation a ≡ b mod m. If they are not congruent we write a 6≡ b
mod m.

TrungDT (FUHN) MAD101 Chapter 3 33 / 45

Modular Arithmetic

Let a, b be integers and m a positive integer. We say a is congruent to b

modulo m is they have the same remainders when being divided by d. We
use notation a ≡ b mod m. If they are not congruent we write a 6≡ b
mod m.

Some properties

TrungDT (FUHN) MAD101 Chapter 3 33 / 45

Modular Arithmetic

Let a, b be integers and m a positive integer. We say a is congruent to b

modulo m is they have the same remainders when being divided by d. We
use notation a ≡ b mod m. If they are not congruent we write a 6≡ b
mod m.

Some properties

a ≡ b mod m ⇐⇒ a − b ≡ 0 mod m ⇐⇒ a = b + km for some

integer k.

TrungDT (FUHN) MAD101 Chapter 3 33 / 45

Modular Arithmetic

Let a, b be integers and m a positive integer. We say a is congruent to b

modulo m is they have the same remainders when being divided by d. We
use notation a ≡ b mod m. If they are not congruent we write a 6≡ b
mod m.

Some properties

a ≡ b mod m ⇐⇒ a − b ≡ 0 mod m ⇐⇒ a = b + km for some

integer k.
If a ≡ b mod m and c ≡ d mod m then a + c ≡ b + d mod m and
ac ≡ bd mod m

TrungDT (FUHN) MAD101 Chapter 3 33 / 45

Applications of Congruences

TrungDT (FUHN) MAD101 Chapter 3 34 / 45

Applications of Congruences

Pseudorandom numbers

TrungDT (FUHN) MAD101 Chapter 3 34 / 45

Applications of Congruences

Pseudorandom numbers

Pseudorandom numbers can be generated using Linear congruential

method:

TrungDT (FUHN) MAD101 Chapter 3 34 / 45

Applications of Congruences

Pseudorandom numbers

Pseudorandom numbers can be generated using Linear congruential

method:

x0 is given, and xn = axn−1 + c mod m, n = 2, 3, 4, . . .

TrungDT (FUHN) MAD101 Chapter 3 34 / 45

Applications of Congruences

Pseudorandom numbers

Pseudorandom numbers can be generated using Linear congruential

method:

x0 is given, and xn = axn−1 + c mod m, n = 2, 3, 4, . . .

m is called the modulus, a is the multiplier, c is the increment and x0 is

the seed.

TrungDT (FUHN) MAD101 Chapter 3 34 / 45

TrungDT (FUHN) MAD101 Chapter 3 35 / 45
Cryptography.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Caesar’s cipher
f (p) = p + 3 mod 26

TrungDT (FUHN) MAD101 Chapter 3 35 / 45

3.5 Primes and Greatest Common Divisors

TrungDT (FUHN) MAD101 Chapter 3 36 / 45

3.5 Primes and Greatest Common Divisors

A positive integer p greater than 1 is called a prime number if the only

prime factors of p are 1 and p.

TrungDT (FUHN) MAD101 Chapter 3 36 / 45

3.5 Primes and Greatest Common Divisors

A positive integer p greater than 1 is called a prime number if the only

prime factors of p are 1 and p. An integer greater than 1 that is not prime
is called composite number.

TrungDT (FUHN) MAD101 Chapter 3 36 / 45

3.5 Primes and Greatest Common Divisors

A positive integer p greater than 1 is called a prime number if the only

prime factors of p are 1 and p. An integer greater than 1 that is not prime
is called composite number.

The Fundamental Theorem of Arithmetic

TrungDT (FUHN) MAD101 Chapter 3 36 / 45

3.5 Primes and Greatest Common Divisors

A positive integer p greater than 1 is called a prime number if the only

prime factors of p are 1 and p. An integer greater than 1 that is not prime
is called composite number.

The Fundamental Theorem of Arithmetic

Any integer greater than 1 can be written uniquely as a product of powers
of distinct primes.

TrungDT (FUHN) MAD101 Chapter 3 36 / 45

3.5 Primes and Greatest Common Divisors

A positive integer p greater than 1 is called a prime number if the only

prime factors of p are 1 and p. An integer greater than 1 that is not prime
is called composite number.

The Fundamental Theorem of Arithmetic

Any integer greater than 1 can be written uniquely as a product of powers
of distinct primes.

Theorem

TrungDT (FUHN) MAD101 Chapter 3 36 / 45

3.5 Primes and Greatest Common Divisors

A positive integer p greater than 1 is called a prime number if the only

prime factors of p are 1 and p. An integer greater than 1 that is not prime
is called composite number.

The Fundamental Theorem of Arithmetic

Any integer greater than 1 can be written uniquely as a product of powers
of distinct primes.

Theorem
There are infinitely many primes.

TrungDT (FUHN) MAD101 Chapter 3 36 / 45

3.5 Primes and Greatest Common Divisors

A positive integer p greater than 1 is called a prime number if the only

prime factors of p are 1 and p. An integer greater than 1 that is not prime
is called composite number.

The Fundamental Theorem of Arithmetic

Any integer greater than 1 can be written uniquely as a product of powers
of distinct primes.

Theorem
There are infinitely many primes.

TrungDT (FUHN) MAD101 Chapter 3 36 / 45

Greatest Common Divisors, Least Common Multiples

TrungDT (FUHN) MAD101 Chapter 3 37 / 45

Greatest Common Divisors, Least Common Multiples
Let a and b be two integers, not both 0. The greatest integer d that
is a divisor of both a and b is called greatest common divisor of a and
b, denoted by gcd(a, b).

TrungDT (FUHN) MAD101 Chapter 3 37 / 45

Greatest Common Divisors, Least Common Multiples
Let a and b be two integers, not both 0. The greatest integer d that
is a divisor of both a and b is called greatest common divisor of a and
b, denoted by gcd(a, b).
Let a and b be two positive integers. The smallest positive integer d
that is divisible by both a and b is called the least common multiple
of a and b, denoted by lcm(a, b).

TrungDT (FUHN) MAD101 Chapter 3 37 / 45

Greatest Common Divisors, Least Common Multiples
Let a and b be two integers, not both 0. The greatest integer d that
is a divisor of both a and b is called greatest common divisor of a and
b, denoted by gcd(a, b).
Let a and b be two positive integers. The smallest positive integer d
that is divisible by both a and b is called the least common multiple
of a and b, denoted by lcm(a, b).

TrungDT (FUHN) MAD101 Chapter 3 37 / 45

Greatest Common Divisors, Least Common Multiples
Let a and b be two integers, not both 0. The greatest integer d that
is a divisor of both a and b is called greatest common divisor of a and
b, denoted by gcd(a, b).
Let a and b be two positive integers. The smallest positive integer d
that is divisible by both a and b is called the least common multiple
of a and b, denoted by lcm(a, b).

To find gcd and lcd of a and b, write a, b as products of powers of distinct

primes.

TrungDT (FUHN) MAD101 Chapter 3 37 / 45

Greatest Common Divisors, Least Common Multiples
Let a and b be two integers, not both 0. The greatest integer d that
is a divisor of both a and b is called greatest common divisor of a and
b, denoted by gcd(a, b).
Let a and b be two positive integers. The smallest positive integer d
that is divisible by both a and b is called the least common multiple
of a and b, denoted by lcm(a, b).

To find gcd and lcd of a and b, write a, b as products of powers of distinct

primes.
a = p1a1 p2a2 · · · pnan
b = p1b1 p2b2 · · · pnbn

TrungDT (FUHN) MAD101 Chapter 3 37 / 45

Greatest Common Divisors, Least Common Multiples
Let a and b be two integers, not both 0. The greatest integer d that
is a divisor of both a and b is called greatest common divisor of a and
b, denoted by gcd(a, b).
Let a and b be two positive integers. The smallest positive integer d
that is divisible by both a and b is called the least common multiple
of a and b, denoted by lcm(a, b).

To find gcd and lcd of a and b, write a, b as products of powers of distinct

primes.
a = p1a1 p2a2 · · · pnan
b = p1b1 p2b2 · · · pnbn
Then:
min(a1 ,b1 ) min(a2 ,b2 ) min(an ,bn )
gcd(a, b) = p1 p2 · · · pn

TrungDT (FUHN) MAD101 Chapter 3 37 / 45

Greatest Common Divisors, Least Common Multiples
Let a and b be two integers, not both 0. The greatest integer d that
is a divisor of both a and b is called greatest common divisor of a and
b, denoted by gcd(a, b).
Let a and b be two positive integers. The smallest positive integer d
that is divisible by both a and b is called the least common multiple
of a and b, denoted by lcm(a, b).

To find gcd and lcd of a and b, write a, b as products of powers of distinct

primes.
a = p1a1 p2a2 · · · pnan
b = p1b1 p2b2 · · · pnbn
Then:
min(a1 ,b1 ) min(a2 ,b2 ) min(an ,bn )
gcd(a, b) = p1 p2 · · · pn
max(a1 ,b1 ) max(a2 ,b2 ) max(an ,bn )
lcm(a, b) = p1 p2 · · · pn
TrungDT (FUHN) MAD101 Chapter 3 37 / 45
Greatest Common Divisors, Least Common Multiples
Let a and b be two integers, not both 0. The greatest integer d that
is a divisor of both a and b is called greatest common divisor of a and
b, denoted by gcd(a, b).
Let a and b be two positive integers. The smallest positive integer d
that is divisible by both a and b is called the least common multiple
of a and b, denoted by lcm(a, b).

To find gcd and lcd of a and b, write a, b as products of powers of distinct

primes.
a = p1a1 p2a2 · · · pnan
b = p1b1 p2b2 · · · pnbn
Then:
min(a1 ,b1 ) min(a2 ,b2 ) min(an ,bn )
gcd(a, b) = p1 p2 · · · pn
max(a1 ,b1 ) max(a2 ,b2 ) max(an ,bn )
lcm(a, b) = p1 p2 · · · pn
TrungDT (FUHN) MAD101 Chapter 3 37 / 45
TrungDT (FUHN) MAD101 Chapter 3 38 / 45
Theorem

TrungDT (FUHN) MAD101 Chapter 3 38 / 45

Theorem
Let a, b be positive integers. Then

TrungDT (FUHN) MAD101 Chapter 3 38 / 45

Theorem
Let a, b be positive integers. Then

ab = gcd(a, b) · lcm(a, b)

TrungDT (FUHN) MAD101 Chapter 3 38 / 45

Theorem
Let a, b be positive integers. Then

ab = gcd(a, b) · lcm(a, b)

Relatively prime
Two integers a, b are called relatively prime if gcd(a, b) = 1.

TrungDT (FUHN) MAD101 Chapter 3 38 / 45

Theorem
Let a, b be positive integers. Then

ab = gcd(a, b) · lcm(a, b)

Relatively prime
Two integers a, b are called relatively prime if gcd(a, b) = 1.
A set of integers are called pairwise relatively prime if any two
integers in the set are relatively prime.

TrungDT (FUHN) MAD101 Chapter 3 38 / 45

Theorem
Let a, b be positive integers. Then

ab = gcd(a, b) · lcm(a, b)

Relatively prime
Two integers a, b are called relatively prime if gcd(a, b) = 1.
A set of integers are called pairwise relatively prime if any two
integers in the set are relatively prime.

Example. Which sets are pairwise relatively prime?

TrungDT (FUHN) MAD101 Chapter 3 38 / 45

Theorem
Let a, b be positive integers. Then

ab = gcd(a, b) · lcm(a, b)

Relatively prime
Two integers a, b are called relatively prime if gcd(a, b) = 1.
A set of integers are called pairwise relatively prime if any two
integers in the set are relatively prime.

Example. Which sets are pairwise relatively prime?

(a) (13, 24, 49)

TrungDT (FUHN) MAD101 Chapter 3 38 / 45

Theorem
Let a, b be positive integers. Then

ab = gcd(a, b) · lcm(a, b)

Relatively prime
Two integers a, b are called relatively prime if gcd(a, b) = 1.
A set of integers are called pairwise relatively prime if any two
integers in the set are relatively prime.

Example. Which sets are pairwise relatively prime?

(a) (13, 24, 49)

(b) (14, 23, 35, 61)

TrungDT (FUHN) MAD101 Chapter 3 38 / 45

3.6 Integers and Algorithms

TrungDT (FUHN) MAD101 Chapter 3 39 / 45

3.6 Integers and Algorithms

Representations of Integers

TrungDT (FUHN) MAD101 Chapter 3 39 / 45

3.6 Integers and Algorithms

Representations of Integers
Let b be an integer greater than 1. Let n be a positive integer. Then n
can be expressed uniquely in the form

n = ak b k + ak−1 b k−1 + · · · + a0 ,

where a0 , a1 , . . . , ak are nonnegative integers and less than b.

TrungDT (FUHN) MAD101 Chapter 3 39 / 45

3.6 Integers and Algorithms

Representations of Integers
Let b be an integer greater than 1. Let n be a positive integer. Then n
can be expressed uniquely in the form

n = ak b k + ak−1 b k−1 + · · · + a0 ,

where a0 , a1 , . . . , ak are nonnegative integers and less than b. This

representation is called base b expansion of n, and is denoted by
n = (ak ak−1 · · · a0 )b .

TrungDT (FUHN) MAD101 Chapter 3 39 / 45

3.6 Integers and Algorithms

Representations of Integers
Let b be an integer greater than 1. Let n be a positive integer. Then n
can be expressed uniquely in the form

n = ak b k + ak−1 b k−1 + · · · + a0 ,

where a0 , a1 , . . . , ak are nonnegative integers and less than b. This

representation is called base b expansion of n, and is denoted by
n = (ak ak−1 · · · a0 )b .

TrungDT (FUHN) MAD101 Chapter 3 39 / 45

TrungDT (FUHN) MAD101 Chapter 3 40 / 45
Some important representations.

TrungDT (FUHN) MAD101 Chapter 3 40 / 45

Some important representations.

Binary expansion: 0, 1

TrungDT (FUHN) MAD101 Chapter 3 40 / 45

Some important representations.

Binary expansion: 0, 1
Octal expansion: 0, 1, 2,..., 7

TrungDT (FUHN) MAD101 Chapter 3 40 / 45

Some important representations.

Binary expansion: 0, 1
Octal expansion: 0, 1, 2,..., 7
Hexadecimal expansion: 0, 1, 2,..., 9, A, B, C, D, E, F

TrungDT (FUHN) MAD101 Chapter 3 40 / 45

Some important representations.

Binary expansion: 0, 1
Octal expansion: 0, 1, 2,..., 7
Hexadecimal expansion: 0, 1, 2,..., 9, A, B, C, D, E, F

Example.

TrungDT (FUHN) MAD101 Chapter 3 40 / 45

Some important representations.

Binary expansion: 0, 1
Octal expansion: 0, 1, 2,..., 7
Hexadecimal expansion: 0, 1, 2,..., 9, A, B, C, D, E, F

Example.

(a) Find the binary expansion of 35

TrungDT (FUHN) MAD101 Chapter 3 40 / 45

Some important representations.

Binary expansion: 0, 1
Octal expansion: 0, 1, 2,..., 7
Hexadecimal expansion: 0, 1, 2,..., 9, A, B, C, D, E, F

Example.

(a) Find the binary expansion of 35

(b) Find the hexadecimal expansion of (132)5

TrungDT (FUHN) MAD101 Chapter 3 40 / 45

Some important representations.

Binary expansion: 0, 1
Octal expansion: 0, 1, 2,..., 7
Hexadecimal expansion: 0, 1, 2,..., 9, A, B, C, D, E, F

Example.

(a) Find the binary expansion of 35

(b) Find the hexadecimal expansion of (132)5

TrungDT (FUHN) MAD101 Chapter 3 40 / 45

TrungDT (FUHN) MAD101 Chapter 3 41 / 45
Hexadecimal, Octal and binary expansions of integers from 0 though 15

TrungDT (FUHN) MAD101 Chapter 3 41 / 45

Hexadecimal, Octal and binary expansions of integers from 0 though 15

Decimal 0 1 2 3 4 5 6 7
Hexadecimal 0 1 2 3 4 5 6 7
Octal 0 1 2 3 4 5 6 7
Binary 0 1 10 11 100 101 110 111
Decimal 8 9 10 11 12 13 14 15
Hexadecimal 8 9 A B C D E F
Octal 10 11 12 13 14 15 16 17
Binary 1000 1001 1010 1011 1100 1101 1110 1111

TrungDT (FUHN) MAD101 Chapter 3 41 / 45

Algorithms for Integer Operations

TrungDT (FUHN) MAD101 Chapter 3 42 / 45

Algorithms for Integer Operations

Let a and b be in the binary expansions.

TrungDT (FUHN) MAD101 Chapter 3 42 / 45

Algorithms for Integer Operations

Let a and b be in the binary expansions.

a = (an−1 an−2 . . . a0 )2 , b = (bn−1 bn−2 . . . b0 )2

Addition algorithm.

TrungDT (FUHN) MAD101 Chapter 3 42 / 45

Algorithms for Integer Operations

Let a and b be in the binary expansions.

a = (an−1 an−2 . . . a0 )2 , b = (bn−1 bn−2 . . . b0 )2

Addition algorithm.

Procedure Addition (a, b)

c := 0
for j := 0 to n − 1
d := b(aj + bj + c)/2c
sj := aj + bj + c − 2d
c := d
sn := c

TrungDT (FUHN) MAD101 Chapter 3 42 / 45

TrungDT (FUHN) MAD101 Chapter 3 43 / 45
Multiplication algorithm.

TrungDT (FUHN) MAD101 Chapter 3 43 / 45

Multiplication algorithm.

a = (an−1 an−2 . . . a0 )2 , b = (bn−1 bn−2 . . . b0 )2

TrungDT (FUHN) MAD101 Chapter 3 43 / 45

Multiplication algorithm.

a = (an−1 an−2 . . . a0 )2 , b = (bn−1 bn−2 . . . b0 )2

Procedure Multiplication (a, b)

for j := 0 to n − 1
if bj = 1 then cj := a shifted j places
else cj := 0
p := 0
for j := 0 to n − 1
p := p + cj

TrungDT (FUHN) MAD101 Chapter 3 43 / 45

Euclidean Algorithm

TrungDT (FUHN) MAD101 Chapter 3 44 / 45

Euclidean Algorithm

Theorem

TrungDT (FUHN) MAD101 Chapter 3 44 / 45

Euclidean Algorithm

Theorem
Let a > b be positive integers. Put r = a mod b. Then

gcd(a, b) = gcd(b, r )

TrungDT (FUHN) MAD101 Chapter 3 44 / 45

Euclidean Algorithm

Theorem
Let a > b be positive integers. Put r = a mod b. Then

gcd(a, b) = gcd(b, r )

Procedure GCD(a, b: positive integers)

x := a
y := b
while y 6= 0
r := x mod y
x := y
y := r

Print(x)

TrungDT (FUHN) MAD101 Chapter 3 44 / 45

Modular Exponentiation

TrungDT (FUHN) MAD101 Chapter 3 45 / 45

Modular Exponentiation

Problem:

TrungDT (FUHN) MAD101 Chapter 3 45 / 45

Modular Exponentiation

Problem: Let b and m be positive integers. Compute b n mod m.

TrungDT (FUHN) MAD101 Chapter 3 45 / 45

Modular Exponentiation

Problem: Let b and m be positive integers. Compute b n mod m.

Example. Compute 371 mod 13.

TrungDT (FUHN) MAD101 Chapter 3 45 / 45

Modular Exponentiation

Problem: Let b and m be positive integers. Compute b n mod m.

Example. Compute 371 mod 13.

Procedure ModExp(b, m: positive integers, n = (ak . . . a0 )2 )

x := 1
power := b mod m
for i := 0 to k
if ai = 1 then x := (x ∗ power ) mod m
power := (power ∗ power ) mod m

Print(x)

TrungDT (FUHN) MAD101 Chapter 3 45 / 45