Chapter 3
Algorithms
Group 3
Table of Contents
01 Complexity of an
algorithm
02 Worst case complexity +
Average-case complexity
03 The worst case complexity of
linear search algorithm
The worst case complexity of
04
bubble sort.
01
Complexity of an
algorithm
When does an
algorithm provide a
satisfactory
solution to a
problem ?
Solution
+ 1. it must always produce the correct
answer. How this can be demonstrated will be
discussed in Chapter 5.
+ 2. it should be efficient. The efficiency of
algorithms will be discussed in this section
How can the efficiency
of an algorithm be
analyzed?
One measure of efficiency
[Link] time complexity
the time used by a
computer to solve a
problem using the
algorithm, when input
values are of a specified
size.
The amountcomplexity
2. space of computer
memory required to
implement the algorithm
when input values are of a
specified size.
DEFINITION
Computational complexity = Time
complexity + space complexity (not be
considered here!).
02
Worst case complexity
Average-case complexity
Ex: Describe the time complexity of the linear search algorithm
=> This is a worst case analysis. Because the largest number of operations
needed to solve the given problem using this algorithm on input of specified
size.
DEFINITION
= 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).
Kahoot
The worst-case
complexity of the
linear search
algorithm
What is the worst-case
complexity of the
linear search algorithm
?
Understanding the Problem
In the Linear Search algorithm, the worst case occurs
when the element to be found is at the end of the list or
not in the list. This means that the algorithm must check
all the elements in the list before the result is determined.
Example
If the original list is [5, 3, 2, 4, 9], then
we need find number ‘9’
Answer
Thuật toán phải kiểm tra từng phần tử một từ 3 đến 9, tổng
cộng 5 lần so sánh.
Conclusion
In the worst case, Linear Search's time complexity is O(n),
where n is the number of elements in the list. This means
that the time required to complete the computation
increases linearly with the number of elements in the list.
The worst-case
complexity of the
bubble sort
What is the worst-
case complexity of
the bubble sort ?
Understanding the Problem
While sorting bubbles, the worst case occurs when the list to be
sorted has been sorted in exactly the opposite order to the
desired order. This means having to change every pair of
elements in succession until there are no more elements that
need to be changed. This requires a maximum number of
iterations, making the algorithm inefficient with large lists.
Example
If the original list is [3, 2, 4, 1, 5], then we need to sort it into [1, 2, 3, 4, 5].
Answer
(5-1).5 20
= = 10
2 2
Conclusion
Thus, in the worst case, bubble sort makes n^2-n comparisons
2
which simplifies to O(n^2) in Big-O notation
