Algorithms The Growth of Functions Complexity of Algorithms

Chapter 3. Algorithms

Mai Văn Duy

Ngày 5 tháng 6 năm 2022

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Contents

1. Algorithms

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Contents

1. Algorithms
2. The Growth of Functions

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Contents

1. Algorithms
2. The Growth of Functions
3. Complexity of Algorithms

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

• Finding the Maximum Element in a Finite Sequence

{8, 4, 11, 3, 10}.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

• 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

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

• 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
• ...

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Definition

An algorithm is a finite sequence of precise instructions for

performing a computation or for solving a problem.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Pseudocode

Pseudocode provides an intermediate step between an

English language description of an algorithm and an
implementation of this algorithm in a programming
language. The steps of the algorithm are specified using
instructions resembling those used in programming
languages.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

PROPERTIES OF ALGORITHMS

• Input. An algorithm has input values from a specified

set.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

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 (solution).

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

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 (solution).
• Definiteness. The steps of an algorithm must be
defined precisely.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

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 (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.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

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 (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.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

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 (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.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

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 (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.
Mai Văn Duy Chapter 3. Algorithms
Algorithms The Growth of Functions Complexity of Algorithms

Finding the Maximum Element in a Finite

Sequence.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Finding the Maximum Element in a Finite

Sequence.

Note: At the first stage, max is a1 and for each the i-th
stage, max is the largest element of first i-th elements of
the considered sequence.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

{8, 4, 11, 3, 10}

Max=8

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

{8, 4, 11, 3, 10}

Max=8
i = 2(8 ≥ 4) → Max=8

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

{8, 4, 11, 3, 10}

Max=8
i = 2(8 ≥ 4) → Max=8
i = 3(8 < 11) → Max=11

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

{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

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

{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

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

{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

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

{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

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

The Linear Search Algorithm

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

The Linear Search Algorithm

Note: The subscript i is increased if x 6= ai , until it reaches

the subscript that x 6= ai . If it is not the case, then i = n + 1.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example: Search for 9 in the list 2, 3, 4, 5, 6, 8, 9, 11:

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

The Binary(nhị phân) Search Algorithm

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

The Binary(nhị phân) Search Algorithm

Note: The algorithm shortens the searching interval until it

reaches the interval which has only one element ai .

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example: Search for 19 in the list

1, 2, 3, 5, 6, 7, 8, 10, 12, 13, 15, 16, 18, 19, 20, 22

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

i=1

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

i=1
j = 16

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

i=1
j = 16
while i < j

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

i=1
j = 16
while i < j
1 + 16
m=b c = b8.5c = 8
2
19 > 16 → i = 8 + 1 = 9

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

i=1
j = 16
while i < j
1 + 16
m=b c = b8.5c = 8
2
19 > 16 → i = 8 + 1 = 9
9 + 16
m=b c = b12.5c = 12
2
19 > 16 → i = 12 + 1 = 13

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

i=1
j = 16
while i < j
1 + 16
m=b c = b8.5c = 8
2
19 > 16 → i = 8 + 1 = 9
9 + 16
m=b c = b12.5c = 12
2
19 > 16 → i = 12 + 1 = 13
13 + 16
m=b c = b14.5c = 14
2
19 ≤ 19 → j = 14

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

i=1
j = 16
while i < j
1 + 16
m=b c = b8.5c = 8
2
19 > 16 → i = 8 + 1 = 9
9 + 16
m=b c = b12.5c = 12
2
19 > 16 → i = 12 + 1 = 13
13 + 16
m=b c = b14.5c = 14
2
19 ≤ 19 → j = 14
13 + 14
m=b c = b13.5c = 13
2
19 > 18 → i = 13 + 1 = 14

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

i=1
j = 16
while i < j
1 + 16
m=b c = b8.5c = 8
2
19 > 16 → i = 8 + 1 = 9
9 + 16
m=b c = b12.5c = 12
2
19 > 16 → i = 12 + 1 = 13
13 + 16
m=b c = b14.5c = 14
2
19 ≤ 19 → j = 14
13 + 14
m=b c = b13.5c = 13
2
19 > 18 → i = 13 + 1 = 14
19 = 19 → location = 14

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Sorting

Sorting is putting the elements into a list in which the

elements are in increasing order.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Sorting

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.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

The Bubble Sort

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

The Bubble Sort

Note: At the first stage, the largest element will be put in

deepest position. Similarly, at the second stage, one does
this for the largest element of the remain...

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example. Use the bubble sort to put 3, 2, 4, 1, 5 into

increasing order.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example. Use the bubble sort to put 3, 2, 4, 1, 5 into

increasing order.
i=1

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example. Use the bubble sort to put 3, 2, 4, 1, 5 into

increasing order.
i=1
j = 1 : 3 > 2 → 2, 3, 4, 1, 5

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example. Use the bubble sort to put 3, 2, 4, 1, 5 into

increasing order.
i=1
j = 1 : 3 > 2 → 2, 3, 4, 1, 5
j = 2 : 3 ≤ 4 → 2, 3, 4, 1, 5

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example. Use the bubble sort to put 3, 2, 4, 1, 5 into

increasing order.
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

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example. Use the bubble sort to put 3, 2, 4, 1, 5 into

increasing order.
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

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example. Use the bubble sort to put 3, 2, 4, 1, 5 into

increasing order.
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

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example. Use the bubble sort to put 3, 2, 4, 1, 5 into

increasing order.
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

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example. Use the bubble sort to put 3, 2, 4, 1, 5 into

increasing order.
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

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example. Use the bubble sort to put 3, 2, 4, 1, 5 into

increasing order.
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

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example. Use the bubble sort to put 3, 2, 4, 1, 5 into

increasing order.
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

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example. Use the bubble sort to put 3, 2, 4, 1, 5 into

increasing order.
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

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example. Use the bubble sort to put 3, 2, 4, 1, 5 into

increasing order.
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

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example. Use the bubble sort to put 3, 2, 4, 1, 5 into

increasing order.
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

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example. Use the bubble sort to put 3, 2, 4, 1, 5 into

increasing order.
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

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

The Insertion Sort

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Note: Begin with the second element. At the first stage

(j = 2), one find the right position of a2 in the first 2
elements of the sequence. If a2 ≤ a1 then one insert a2
into the front of a1 (a1 now is labeled as a2 ). In the
general, one find the right position of aj in list of the first j
elements and inserts it into this position (the remain must
be put 1 step backward).

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example. Use the insertion sort to put the elements of the

list 3, 2, 4, 1, 5 in increasing order.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Big-O Notation

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Big-O Notation

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

Show that f (x ) = x 2 + 2x + 1 is O (x 2 ).

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

Show that f (x ) = x 2 + 2x + 1 is O (x 2 ).
Solution.
∀x > 1 =⇒ x 2 > 1 ∧ x 2 > x

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

Show that f (x ) = x 2 + 2x + 1 is O (x 2 ).
Solution.
∀x > 1 =⇒ x 2 > 1 ∧ x 2 > x
f (x ) = x 2 + 2x + 1 < x 2 + 2x 2 + x 2 = 4x 2

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

Show that f (x ) = x 2 + 2x + 1 is O (x 2 ).
Solution.
∀x > 1 =⇒ x 2 > 1 ∧ x 2 > x
f (x ) = x 2 + 2x + 1 < x 2 + 2x 2 + x 2 = 4x 2
Let g (x ) = x 2

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

Show that f (x ) = x 2 + 2x + 1 is O (x 2 ).
Solution.
∀x > 1 =⇒ x 2 > 1 ∧ x 2 > x
f (x ) = x 2 + 2x + 1 < x 2 + 2x 2 + x 2 = 4x 2
Let g (x ) = x 2
We have C = 4, k = 1, |f (x )| ≤ C |g (x )|

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

Show that f (x ) = x 2 + 2x + 1 is O (x 2 ).
Solution.
∀x > 1 =⇒ x 2 > 1 ∧ x 2 > x
f (x ) = x 2 + 2x + 1 < x 2 + 2x 2 + x 2 = 4x 2
Let g (x ) = x 2
We have C = 4, k = 1, |f (x )| ≤ C |g (x )|
Thus, f (x ) is O (x 2 )

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Big-O theorem

1. Let f (x ) = an x n + an−1 x n−1 + ... + a1 x + a0 where

a1 , a2 , ....an−1 , an are real numbers. Then, f (x ) is O (x n ).

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Big-O theorem

1. Let f (x ) = an x n + an−1 x n−1 + ... + a1 x + a0 where

a1 , a2 , ....an−1 , an are real numbers. Then, f (x ) is O (x n ).
2. f1 (x ) = O (g1 (x )) ∧ f2 (x ) = O (g2 (x ))

=⇒ (f1 + f2 )(x ) = O (max (|g1 (x )|, |g2 (x )|))

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Big-O theorem

1. Let f (x ) = an x n + an−1 x n−1 + ... + a1 x + a0 where

a1 , a2 , ....an−1 , an are real numbers. Then, f (x ) is O (x n ).
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 ))

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Big-O theorem

1. Let f (x ) = an x n + an−1 x n−1 + ... + a1 x + a0 where

a1 , a2 , ....an−1 , an are real numbers. Then, f (x ) is O (x n ).
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 ))

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Big-O theorem

1. Let f (x ) = an x n + an−1 x n−1 + ... + a1 x + a0 where

a1 , a2 , ....an−1 , an are real numbers. Then, f (x ) is O (x n ).
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 )).

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

The growth of functions commonly used in big-O

estimates.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

1. Give a big-O estimate for

f (n) = 3n log(n!) + (n2 + 3) log n, where n is a positive
integer.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

1. Give a big-O estimate for

f (n) = 3n log(n!) + (n2 + 3) log n, where n is a positive
integer.
2. Give a big-O estimate for
f (x ) = (x + 1) log(x 2 + 1) + 3x 2 .

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Solution.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Quizz

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Quizz

Ans: C

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Quizz

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Quizz

Ans: a,b.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Quizz

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Quizz

Ans: a
Mai Văn Duy Chapter 3. Algorithms
Algorithms The Growth of Functions Complexity of Algorithms

Big-Omega and Big-Theta Notation

• ∃C > 0, k : x ≥ k ∧ |f (x )|≥C |g (x )| → f (x ) = Ω(g (x ))

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Big-Omega and Big-Theta Notation

• ∃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 ))

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Big-Omega and Big-Theta Notation

• ∃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 ))

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Big-Omega and Big-Theta Notation

• ∃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 )

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Big-Omega and Big-Theta Notation

• ∃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

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Big-Omega and Big-Theta Notation

• ∃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 )

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Big-Omega and Big-Theta Notation

• ∃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 )).

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Big-Omega and Big-Theta Notation

• ∃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 bậc).

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Big-Omega and Big-Theta Notation

• ∃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 bậc).
3. Let f (x ) = an x n + an−1 x n−1 + ... + a1 x + a0 where
a1 , a2 , ....an−1 , an are real numbers. Then, f (x ) is Θ(x n ).

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Introduction

• Computational complexity = Time complexity +

space complexity (not be considered).

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Introduction

• 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.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Introduction

• 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.).

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Introduction

• 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).

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

{8, 4, 11, 3, 10}

Max=8

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

{8, 4, 11, 3, 10}

Max=8
i = 2 ≤ 5(8 ≥ 4) → Max=8

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

{8, 4, 11, 3, 10}

Max=8
i = 2 ≤ 5(8 ≥ 4) → Max=8
i = 3 ≤ 5(8 < 11) → Max=11

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

{8, 4, 11, 3, 10}

Max=8
i = 2 ≤ 5(8 ≥ 4) → Max=8
i = 3 ≤ 5(8 < 11) → Max=11
i = 4 ≤ 5(11 ≥ 3) → Max=11

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

{8, 4, 11, 3, 10}

Max=8
i = 2 ≤ 5(8 ≥ 4) → Max=8
i = 3 ≤ 5(8 < 11) → Max=11
i = 4 ≤ 5(11 ≥ 3) → Max=11
i = 5 ≤ 5(11 ≥ 10) → Max=11

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

{8, 4, 11, 3, 10}

Max=8
i = 2 ≤ 5(8 ≥ 4) → Max=8
i = 3 ≤ 5(8 < 11) → Max=11
i = 4 ≤ 5(11 ≥ 3) → Max=11
i = 5 ≤ 5(11 ≥ 10) → Max=11

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

{8, 4, 11, 3, 10}

Max=8
i = 2 ≤ 5(8 ≥ 4) → Max=8
i = 3 ≤ 5(8 < 11) → Max=11
i = 4 ≤ 5(11 ≥ 3) → Max=11
i = 5 ≤ 5(11 ≥ 10) → Max=11
Thus, Max=11

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

Describe the time complexity (Worst-case) of the

algorithm for finding the largest element in a set.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

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.

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Example.

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) + [Link],

f (x ) = Θ (n).

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Quizz

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Quizz

Ans: b (Number of comparisons f (n) = 2n + 1)

Mai Văn Duy Chapter 3. Algorithms
Algorithms The Growth of Functions Complexity of Algorithms

Quizz

Mai Văn Duy Chapter 3. Algorithms

Algorithms The Growth of Functions Complexity of Algorithms

Quizz

Ans: a (f (n) = n)

Mai Văn Duy Chapter 3. Algorithms