Chapter 3
Algorithms
MAD101
Ly Anh Duong
duongla3@fe.edu.vn
Table of Contents
1 Algorithms
▶ Algorithms
▶ The Growth of Functions
▶ Complexity of Algorithms
▶ Problems
Example.
1 Algorithms
• Finding the Maximum Element in a Finite Sequence {8, 4, 11, 3, 10}.
• To search for 19 in the list 1, 2, 3, 5, 6, 7, 8, 10, 12, 13, 15, 16, 18, 19, 20, 22
• ...
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 3 / 54
Definition
1 Algorithms
An algorithm is a finite sequence of precise instructions (mã lệnh xác định) for
performing a computation or for solving a problem.
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 4 / 54
PROPERTIES OF ALGORITHMS
1 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 (solution).
• 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
(but perhaps large) number of steps for any input in the set.
• Effectiveness. It must be possible to perform each step of an algorithm
exactly and in a finite amount of time.
• Generality. The procedure should be applicable for all problems of the
desired form.
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 5 / 54
Finding the Maximum Element in a Finite
Sequence.
1 Algorithms
Example. Finding the Maximum Element in a Finite Sequence {8, 4, 11, 3, 10}.
procedure max (a1 , a2 , a3 , a4 , a5 : integers)
max:=a1
for i:=2 to 5
if max < ai then max:= ai
return max {max is the largest element}
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 6 / 54
Example.
1 Algorithms
{8, 4, 11, 3, 10}
Max=8
i = 2(8 ≥ 4) → Max=8
i = 3(8 < 11) → Max=11
i = 4(11 ≥ 3) → Max=11
i = 5(11 ≥ 10) → Max=11
Thus, Max=11
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 7 / 54
The Linear Search Algorithm
1 Algorithms
Example. List all the steps used to search for 9 in the sequence 2, 3, 4, 5, 6, 8, 9, 11
using a linear search. How many comparisons required to search for 9 in the
sequence.
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 8 / 54
Solution
1 Algorithms
Below is the linear search algorithm in pseudocode
2, 3, 4, 5, 6, 8, 9, 11
procedure linear search (x: integer, a1 , a2 , ..., a8 : distinct integers)
i := 1
while (i ≤ 8 and x ̸= ai )
i := i + 1
if i ≤ 8 then location: = i
else location: = 0
return location {location is the subscript of the term that equals x, or is 0 if
x is not found}
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 9 / 54
2, 3, 4, 5, 6, 8, 9, 11
1 Algorithms
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 10 / 54
The Binary(nhị phân) Search Algorithm
1 Algorithms
Example. To search for 19 in the list 1, 2, 3, 5, 6, 7, 8, 10, 12, 13, 15, 16, 18, 19, 20, 22
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 11 / 54
Solution
1 Algorithms
1, 2, 3, 5, 6, 7, 8, 10, 12, 13, 15, 16, 18, 19, 20, 22. Search 19
procedure binary search ( x:integer, a1 , a2 , . . . , a16 : increasing integers)
i := 1 { i is left endpoint of search interval}
j := 16 { j is right endpoint of search interval}
while i < j
m := ⌊(i + j)/2⌋
if x > am then i := m + 1
else j := m
if x = ai then location: = i
else location: = 0
return location {location is the subscript of the term that equals x, or is 0 if
x is not found}
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 12 / 54
1, 2, 3, 5, 6, 7, 8, 10, 12, 13, 15, 16, 18, 19, 20, 22. Search
19
1 Algorithms
i=1
j = 16
while i < j
1 + 16
m=⌊ ⌋ = ⌊8.5⌋ = 8
2
19 > 16 → i = 8 + 1 = 9, 19 ̸= 12 →location:=0
9 + 16
m=⌊ ⌋ = ⌊12.5⌋ = 12
2
19 > 16 → i = 12 + 1 = 13, 19 ̸= 18 →location:=0
13 + 16
m=⌊ ⌋ = ⌊14.5⌋ = 14
2
19 ≤ 19 → j = 14, 19 ̸= 18 →location:=0
13 + 14
m=⌊ ⌋ = ⌊13.5⌋ = 13
2
19 > 18 → i = 13 + 1 = 14
19Anh
Ly = 19 → location
Duong = 14 Chapter 3 Algorithms duongla3@fe.edu.vn 13 / 54
Sorting
1 Algorithms
Sorting is putting the elements into a list in which the elements are in increasing
order.
For instance, sorting the list 7, 2, 1, 4, 5, 9 produces the list 1, 2, 4, 5, 7, 9. Sorting
the list d, h, c, a, f (using alphabetical order) produces the list a, c, d, f, h.
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 14 / 54
The Bubble Sort
1 Algorithms
Example. Use the bubble sort to put 3, 2, 4, 1, 5 into increasing order.
procedure bubble sort (a1 , a2 , . . . , a5 :real numbers with 5 ≥ 2)
for i := 1 to 4
for j := 1 to 5 − i
if aj > aj+1 then interchange aj and aj+1
{a1 , a2 , . . . , a5 is in increasing order}
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 15 / 54
Use the bubble sort to put 3, 2, 4, 1, 5 into
increasing order
1 Algorithms
i=1
j = 1 : 3 > 2 → 2, 3, 4, 1, 5
j = 2 : 3 ≤ 4 → 2, 3, 4, 1, 5
j = 3 : 4 > 1 → 2, 3, 1, 4, 5
j = 4 : 4 ≤ 5 → 2, 3, 1, 4, 5
i=2
j = 1 : 2 ≤ 3 → 2, 3, 1, 4, 5
j = 2 : 3 > 1 → 2, 1, 3, 4, 5
j = 3 : 3 ≤ 4 → 2, 1, 3, 4, 5
i=3
j = 1 : 2 > 1 → 1, 2, 3, 4, 5
j = 2 : 2 ≤ 3 → 1, 2, 3, 4, 5
i=4
j = 1 : 1 ≤ 2 → 1, 2, 3, 4, 5
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 16 / 54
Use the bubble sort to put 3, 2, 4, 1, 5 into
increasing order
1 Algorithms
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 17 / 54
The Insertion Sort
1 Algorithms
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 18 / 54
Use the insertion sort to put the elements of
the list 3, 2, 4, 1, 5 in increasing order
1 Algorithms
procedure insertion sort (a1 , a2 , . . . , a5 :real numbers with 5 ≥ 2)
for j := 2 to 5 { j: position of the examined element }
{ finding out the right position of aj }
i := 1
while aj > ai
i := i + 1
m := aj { save aj }
{ moving j-i elements backward }
for k := 0 to j − i − 1
aj−k := aj−k−1
{move aj to the position i}
ai := m
{a1 , a2 , . . . , a5 is increasing order}
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 19 / 54
3, 2, 4, 1, 5
1 Algorithms
j=2
i = 1, 2 ≤ 3 → i = 1, m = 2
k = 0 → a2 = 3, a1 = 2
→ 2, 3, 4, 1, 5
j=3
i = 1, 4 > 2
i = 2, 4 > 3
→ 2, 3, 4, 1, 5
j=4
i = 1, 1 ≤ 2 → i = 1, m = 1
k = 0 → a4 = 4
k = 1 → a3 = 3
k = 2 → a2 = 2
a1 = 1
→ 1, 2, 3, 4, 5
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 20 / 54
3, 2, 4, 1, 5
1 Algorithms
j=4
i = 1, 1 ≤ 2 → i = 1, m = 1
k = 0 → a4 = 4
k = 1 → a3 = 3
k = 2 → a2 = 2
a1 = 1
→ 1, 2, 3, 4, 5
j=5
i = 1, 5 > 1
i = 2, 5 > 2
i = 3, 5 > 3
i = 4, 5 > 4
Thus, → 1, 2, 3, 4, 5
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 21 / 54
Table of Contents
2 The Growth of Functions
▶ Algorithms
▶ The Growth of Functions
▶ Complexity of Algorithms
▶ Problems
Introduction
2 The Growth of Functions
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 23 / 54
Example.
2 The Growth of Functions
(constant that mean f (n) = k, ∀n. In this ex, k = 1)
→ 1 < log2 n(≡ logn) < n < n2 < 2n < n!
• Growth of logn < growth of n → logn is O(n)
• In general, growth of f (n) ≤ growth of g(n) → f (n) is O(g(n))
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 24 / 54
Big-O Notation
2 The Growth of Functions
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 25 / 54
Example.
2 The Growth of Functions
Show that f (x) = x2 + 2x + 1 is O(x2 ).
Solution.
∀x > 1 =⇒ x2 > 1 ∧ x2 > x
f (x) = x2 + 2x + 1 < x2 + 2x2 + x2 = 4x2
Let g(x) = x2
We have C = 4, k = 1, |f (x)| ≤ C|g(x)|
Thus, f (x) is O(x2 )
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 26 / 54
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 27 / 54
The growth of functions commonly used in
big-O estimates.
2 The Growth of Functions
1 < logn < n < nlogn < n2 < 2n < n!
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 28 / 54
The growth of functions commonly used in
big-O estimates.
2 The Growth of Functions
1 < logn < n < nlogn < n2 < 2n < n!
How about n3 , 3n and 4n2 ?
Note. Cf (n) ∼ f (n) , C is constant.
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 29 / 54
Big-O theorem
2 The Growth of Functions
1. Let f (x) = an xn + an−1 xn−1 + ... + a1 x + a0 where a1 , a2 , ....an−1 , an are real
numbers. Then, f (x) is O(xn ).
2. f1 (x) = O(g1 (x)) ∧ f2 (x) = O(g2 (x))
=⇒ (f1 + f2 )(x) = O(max(|g1 (x)|, |g2 (x)|))
3. f1 (x) = O(g1 (x)) ∧ f2 (x) = O(g2 (x))
=⇒ (f1 f2 )(x) = O(g1 g2 (x))
COROLLARY. Suppose that f1 (x) and f2 (x) are both O(g(x)). Then
(f1 + f2 )(x) is O(g(x)).
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 30 / 54
Example.
2 The Growth of Functions
1. Estimate big-oh of functions 100n2 + 23nlogn + 2019
2. Give a big-O estimate for (2n2 + 17n)(7logn + 15)
3. Give a big-O estimate for f (n) = 3nlog(n!) + (n2 + 3)logn, where n is a
positive integer.
4. Give a big-O estimate for f (x) = (x + 1)log(x2 + 1) + 3x2 .
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 31 / 54
Solution.
2 The Growth of Functions
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 32 / 54
Quizz
2 The Growth of Functions
Ans: C
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 33 / 54
Quizz
2 The Growth of Functions
Ans: a,b (hàm nào có O(n))(f (x) = O(g(x)) mean f(x) is big-oh of g(x))
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 34 / 54
Quizz
2 The Growth of Functions
Ans: a
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 35 / 54
Big-Omega and Big-Theta Notation
2 The Growth of Functions
• ∃C > 0, k : x ≥ k ∧ |f (x)|≥C|g(x)| → f (x) = Ω(g(x))
• f (x) = O(g(x)) ∧ f (x) = Ω(g(x)) → f (x) = Θ(g(x))
Example. Show that f (x) = 1 + 2 + ... + n is Θ(n2 )
n(n + 1) n2
f (x) = 1 + 2 + ... + n = =⇒ ≤ f (x) ≤ n2
2 2
=⇒ f (x) = Ω(n2 ) ∧ f (x) = Θ(n2 ) =⇒ f (x) = Θ(n2 )
Notes.
1. f (x) is Ω(g(x)) if and only if g(x) is O(f (x)).
2. If f (x) = Θ(g(x)) then f(x) is of order g(x) or f(x) and g(x) are of the same
order (cùng độ tăng).
3. Let f (x) = an xn + an−1 xn−1 + ... + a1 x + a0 where a1 , a2 , ....an−1 , an are real
numbers. Then, f (x) is Θ(xn ).
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 36 / 54
Table of Contents
3 Complexity of Algorithms
▶ Algorithms
▶ The Growth of Functions
▶ Complexity of Algorithms
▶ Problems
Introduction
3 Complexity of Algorithms
• Computational complexity = Time complexity + space complexity (not be
considered).
• Time complexity can be expressed in terms of the number of operations used
by the algorithm.
1. Worst-case complexity (tells us how many operations an algorithm requires to
guarantee that it will produce a solution.).
2. Average-case complexity (the average number of operations used to solve the
problem over all possible inputs of a given size).
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 38 / 54
Example.
3 Complexity of Algorithms
{8, 4, 11, 3, 10}
Max=8
i = 2(8 ≥ 4) → Max=8
i = 3(8 < 11) → Max=11
i = 4(11 ≥ 3) → Max=11
i = 5(11 ≥ 10) → Max=11
Thus, Max=11
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 39 / 54
Example.
3 Complexity of Algorithms
Describe the time complexity (Worst-case) of the algorithm for finding the largest
element in a set.
→ Number of comparisons f (n) = 2(n − 1) + 1. Thus, f (x) = Θ(n).
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 40 / 54
Example.
3 Complexity of Algorithms
Ans:f(n)=n+n=2n is O(n)
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 41 / 54
Example.
3 Complexity of Algorithms
Ans: f (n) = n.n = n2 is O(n2 )
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 42 / 54
Example.
3 Complexity of Algorithms
Ans: f (n) = n + n2 is O(n2 )
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 43 / 54
Quizz
3 Complexity of Algorithms
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 44 / 54
Quizz
3 Complexity of Algorithms
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 45 / 54
Table of Contents
4 Problems
▶ Algorithms
▶ The Growth of Functions
▶ Complexity of Algorithms
▶ Problems
Algorithms
4 Problems
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 47 / 54
Algorithms
4 Problems
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 48 / 54
The Growth of Functions
4 Problems
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 49 / 54
The Growth of Functions
4 Problems
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 50 / 54
Complexity of Algorithms
4 Problems
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 51 / 54
Complexity of Algorithms
4 Problems
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 52 / 54
Complexity of Algorithms
4 Problems
Ly Anh Duong Chapter 3 Algorithms duongla3@fe.edu.vn 53 / 54
Q&A
Thank you for listening!
