DATA STRUCTURES

& ALGORITHMS
Lecture 1: Introduction to
Algorithms & Algorithm Analysis
Lecturer: Dr. Nguyen Hai Minh
CONTENT
 Role of Algorithms in Computing
 Algorithm Analysis Framework
 Asymptotic Annotations
 Mathematical Analysis of Algorithm

5/30/2023 Nguyen Hai Minh 2

ROLE OF ALGORITHMS IN
COMPUTING

5/30/2023 Nguyen Hai Minh 3

What is Algorithm?
Input
 Algorithm:
◼ well-defined
computational
Computational
procedure that steps
takes some value,
or set of values,
as input and
produces some
Output
value, or set of
values, as output Computational Problem

5/30/2023 Nguyen Hai Minh 4

Why should we study algorithm?
 Computer programs would not exist without
algorithms.
 Studying algorithms help developing analytical skill
◼ It can be seen as special kinds of solutions to problems
– not just answer but precisely defined procedures for
getting answers.
◼ Consequently, specific algorithm design techniques can
be interpreted as problem-solving strategies that can be
useful in other fields, not just in computing.
→ Algorithmic thinking
5/30/2023 Nguyen Hai Minh 5
Why should we study algorithm?
A person well-trained in computer science
knows how to deal with algorithms: how to
construct them, manipulate them,
understand them, analyze them.

- Donald Knuth -

5/30/2023 Nguyen Hai Minh 6

What kind of problems are solved by Algorithm?

➢ Sorting
➢ Searching
➢ String matching
➢ Graph problems
➢ Combinatorial problems
➢ Geometric problems
➢ Numerical problems
→ These problems are introduced in the subsequent
lectures to illustrate different algorithm design
techniques and methods of algorithm analysis
5/30/2023 Nguyen Hai Minh 7
Problems that cannot be solved by Algorithm?

 The precision inherently imposed by algorithmic

thinking limits the kinds of problems that can be
solved with an algorithm.
 You will not find algorithms for:
◼ Living a happy life
◼ Becoming a millionaire
◼ Living forever
◼ …

5/30/2023 Nguyen Hai Minh 8

Algorithmic Problem Solving
Decide on:
Understand Computational means, exact
the problem vs. approximate solving,
algorithm design technique

Design algorithm &

data structure

Prove correctness

Analyze the algorithm

Code the algorithm

5/30/2023 Nguyen Hai Minh 9

Designing Algorithms
 Brute-force &  Dynamic
Exhaustive Search Programming
 Decrease and  Greedy Technique
Conquer  Iterative Improvement
 Divide and Conquer  Backtracking
 Transform and  Branch-and-bound
Conquer  Approximation
 Space and Time algorithms
Trade-offs
5/30/2023 Nguyen Hai Minh 10
Designing Data Structure
 Linear Data Structure:
◼ Array
◼ Linked List
◼ Stack
◼ Queue
◼ Hash Table
 Trees
 Graphs

5/30/2023 Nguyen Hai Minh 11

ALGORITHM ANALYSIS
FRAMEWORK
Measuring an Input’s size
Units for Measuring Running Time
Order of Growth
Kinds of Analysis
Nguyen Hai Minh 12
Algorithm Analysis
 The theoretical study of computer-program
performance and resource usage.
◼ Time efficiency
◼ Space efficiency
 What is more important than performance?
o modularity o user-friendliness
o correctness o programmer time
o maintainability o simplicity
o functionality o extensibility
o robustness o reliability
5/30/2023 Nguyen Hai Minh 13
Algorithm Analysis
 Nowadays, the amount of extra space required
by an algorithm is typically not of as much
concern.
 In most problems, we can achieve much more
spectacular progress in speed than in space.
→ We primarily concentrate on time efficiency, but
analytical framework in this course is applicable to
analyzing space efficiency as well.

5/30/2023 Nguyen Hai Minh 14

Performance (efficiency) of Algorithms
 Performance often draws the line between
what is feasible and what is impossible.
 Algorithmic mathematics provides a language
for talking about program behavior.
 Performance is the currency of computing.
 The lessons of program performance
generalize to other computing resources.
 Speed is fun!

5/30/2023 Nguyen Hai Minh 15

Measuring an Input’s Size
 Almost all algorithms run longer on larger
inputs.
 For example:
◼ Sorting arrays: A1 = {12, 1, 3}
◼ Sorting arrays: A2 = {88, 12, 3, 19, 32, 9, 1, 3, 45,
17, 89, 12, 34, 52, 61, 41, 24, 98, 19, 38}
 Algorithm’s efficiency is investigated as a
function of some parameter n indicating the
algorithm’s input size.

5/30/2023 Nguyen Hai Minh 16

Measuring an Input’s Size
 Straightforward: problems dealing with lists
(e.g., sorting, searching, min, max, …)
◼ n is the size of the list
 Not straightforward:
◼ Computing the product of two matrix
◼ Checking primality of a positive integer n
◼ Finding GCD of two numbers
◼ Spell-checking a document
◼ …
5/30/2023 Nguyen Hai Minh 17
Units for Measuring Running Time
 Algorithm’s running time depends on:
◼ Computer speed (hardware, software).
◼ Using resource (memory, disk).
◼ Implementation of algorithm
 How to analyze running time correctly?
◼ Ignore machine-dependent time
◼ Using “logic” metrics (ex: numbers of operations: +,-
,*,/,<,>,=…) rather than real time metrics (mili-
seconds, seconds, minutes, hours, …)

Machine-independent Time
5/30/2023 Nguyen Hai Minh 18
Units for Measuring Running Time
 Count the number of primitive operations or steps
executed (the most time-consuming operation in
the algorithm’s innermost loop)
 For example:
◼ Most sorting algorithms work by comparing
elements (keys) of a list & exchanging elements →
basic operation is key comparison (<, >, ==) and
assignment (=)
 Then, running time of an algorithm can be seen as
a cost function that depends on the size of input.
5/30/2023 Nguyen Hai Minh 19
Units for Measuring Running Time
 Sum of n integer:
sum = 0;
for (i = 0; i < n; i++) Assignment: 2n+2
sum = sum + i;

sum = 0;
for (i = 0; i < n; i++) Comparison: n+1
sum = sum + i;

 Running time: 𝑇(𝑛) = 3𝑛 + 3

5/30/2023 Nguyen Hai Minh 20

Order of Growth
 We should focus on the count’s order of
growth for large input size!
◼ For small inputs, the difference in running time is
not what really distinguishes efficient algorithms
from inefficient ones.
◼ Example: powering a number by n
 Decrease-by-one technique
 Divide-and-Conquer technique
→ The efficiency of two algorithms becomes clear and
important when n is large.

5/30/2023 Nguyen Hai Minh 21

Order of Growth (Rate of Growth)
 For large values of n (𝑛 → ∞), the function’s
order of growth is important!
◼ The growth of 𝑇 depends on 𝑛

Value Value % Value %

1 303 300 99.01 3 0.66
1000 3,003 3,000 99.93 3 0.07
10,000 30,003 30,000 99.99 3 0.01
100,000 300,003 300,000 100 3 0.00

◼ Ignore very small parts in the cost function.

◼ 𝑇(𝑛) = 3𝒏 + 3

5/30/2023 Nguyen Hai Minh 22

 Order of Growth (Rate of Growth)
 Another example:

Value Value % Value % Value % Value %

1 1,101 1 0.1 100 9.1 0 0.0 1,000 90.82
10 2,101 100 4.76 1,000 47.6 1 0.05 1,000 47.62
100 21,002 10,000 47.6 10,000 47.6 2 0.991 1,000 4.76
1,000 1,101,003 1,000,000 90.8 100,000 9.1 3 0.0003 1,000 0.09
10,000 101,001,004 100,000,000 99.0 1,000,000 0.99 4 0.0 1,000 0.001
100,000 10,010,001,005 10,000,000,000 99.9 10,000,000 0.099 5 0.0 1,000 0.0

T(n) = 3n2 + log10n + 1000

➔ The growth of T depends on n2

5/30/2023 Nguyen Hai Minh 23

Comparison of functions

1 log2 n n n log2 n n2 n3 2n n!
1 0 1 0 1 1 2 1
1 1 2 2 4 8 4 2
1 2 4 8 16 64 16 24
1 3 8 24 64 512 256 40,320
1 4 16 64 256 4096 65,536 2.092279*1013
1 5 32 160 1,024 32,768 4,294,967,296 2.6313084*1035

5/30/2023 Nguyen Hai Minh 24

Kinds of analyses
 There are many algorithms for which running
time depends not only on input size but also on
the specifics of a particular input.
 For example: Insertion Sort runs fastest if the
array is already sorted, slowest if the array is in
decreasing order.

5/30/2023 Nguyen Hai Minh 25

Kinds of analyses
 Worst-case: (usually)
• T(n) = maximum time of algorithm on any input of
size n.
 Average-case: (sometimes)
• T(n) = expected time of algorithm over all inputs
of size n.
→ Need assumption of statistical distribution
of inputs.
 Best-case: (bogus)
→ Cheat with a slow algorithm that works fast
on some input.
5/30/2023 Nguyen Hai Minh 26
Kinds of analyses

5 worst-case

4
Running Time (ms)

average-
3 case

2 best-case

1
Generally, we seek
0
upper bounds on the
A B C D E F running time,
Input Instance because everybody
likes a guarantee.
5/30/2023 Nguyen Hai Minh 27
 Insertion Sort Analysis
INSERTION-SORT(A,n) Cost times
1 for i = 2 to n c1 𝑛
2 key = A[i] c2 𝑛−1
3 //Insert A[i] into the sorted subarray A[1:i-1] 0 𝑛−1
4 j = i – 1 c4 𝑛−1
5 while j > 0 and A[j] > key c5 σ𝑛𝑖=2 𝑡𝑖
6 A[j+1] = A[j] c6 σ𝑛𝑖=2(𝑡𝑖 −1)
7 j = j – 1 c7 σ𝑛𝑖=2(𝑡𝑖 −1)
8 A[j+1] = key c8 𝑛 − 1
𝒏 𝒏 𝒏
𝑻 𝒏 = 𝒄𝟏 𝒏 + 𝒄𝟐 𝒏 − 𝟏 + 𝒄𝟒 𝒏 − 𝟏 + 𝒄𝟓 ෍ 𝒕𝒊 + 𝒄𝟔 ෍ (𝒕𝒊 −𝟏) + 𝒄𝟕 ෍ (𝒕𝒊 −𝟏) + 𝒄𝟖 𝒏 − 𝟏
𝒊=𝟐 𝒊=𝟐 𝒊=𝟐

5/30/2023 Nguyen Hai Minh 28

Insertion Sort Analysis
 Best case: the array has been sorted
◼ While loop always exists upon the first test in line 5
◼ Therefore, ti = 1 for all i = 2, …, n
◼ The best case running time is given by:

𝑇 𝑛 = 𝑐1 𝑛 + 𝑐2 𝑛 − 1 + 𝑐4 𝑛 − 1 + 𝑐5 𝑛 − 1 + 𝑐8 𝑛 − 1
= 𝑐1 + 𝑐2 + 𝑐4 + 𝑐8 𝑛 − 𝑐2 + 𝑐4 + 𝑐5 + 𝑐8 = 𝑎𝑛 + 𝑏

→ The running time is thus a linear function of n

5/30/2023 Nguyen Hai Minh 29

Insertion Sort Analysis
 Worst case: the array is in reverted sorted
◼ The procedure must compare each element A[i] with each
element in the entire sorted subarray
◼ Therefore, ti = i for all i = 2, …, n
◼ The worst case running time is given by:
𝑛(𝑛 − 1)
𝑇 𝑛 = 𝑐1 𝑛 + 𝑐2 𝑛 − 1 + 𝑐4 𝑛 − 1 + 𝑐5 −1
2
𝑛(𝑛 − 1) 𝑛(𝑛 − 1)
+𝑐6 + 𝑐6 + 𝑐8 𝑛 − 1
2 2
𝑐5 𝑐6 𝑐7 2 𝑐5 𝑐6 𝑐7
= + + 𝑛 + 𝑐1 + 𝑐2 + 𝑐4+ − − + 𝑐8 𝑛
2 2 2 2 2 2
− 𝑐2 + 𝑐4 + 𝑐5 + 𝑐8 = 𝑎𝑛2 + 𝑏𝑛 + 𝑐

→ The running time is thus a quadratic function of n

5/30/2023 Nguyen Hai Minh 30
Insertion Sort Analysis
 Average case: the array is in randomly chosen
number.
◼ On average, half the elements in A[1 : i – 1] are
less than A[i], and half the elements are greater.
◼ Therefore, ti = i/2 for i = 2, …, n
◼ The average case running time is thus a
quadratic function of n

5/30/2023 Nguyen Hai Minh 31

ASYMPTOTIC NOTATIONS
Big-O notation
Basic Efficiency Classes

5/30/2023 Nguyen Hai Minh 32

Asymptotic Analysis

Look at growth of 𝒇(𝒏) as 𝒏 → ∞

“Asymptotic Analysis”

5/30/2023 Nguyen Hai Minh 33

Asymptotic Notations
 Efficiency analysis concentrates on the order of
growth of an algorithm’s basic operation count.
 To compare such order of growth, computer
scientists use 3 notations:

𝜪 Big-Oh
Ω Big Omega
𝜣 Big Theta

5/30/2023 Nguyen Hai Minh 34

Asymptotic Notations – Big-Oh
 𝑶 𝒈 𝒏 : set of all functions with a lower or
same order of growth as 𝑔 𝑛
1
◼ E.g., 𝑛 ∈ 𝑂 𝑛2 , 100𝑛 + 5 ∈ 𝑂 𝑛2 , 𝑛(𝑛 − 1) ∈ 𝑂 𝑛2
2
◼ 𝑛3 ∉ 𝑂 𝑛2 , 0.0001𝑛3 ∉ 𝑂 𝑛2 , 𝑛4 + 𝑛 + 1 ∉ 𝑂 𝑛2

f(n)

𝒇(𝒏) ∈ 𝑶 𝒈(𝒏)

5/30/2023 Nguyen Hai Minh 35

Asymptotic Notations – Big Omega
 𝜴 𝒈 𝒏 : set of all functions with a higher or
same order of growth as 𝑔 𝑛
1
◼ E.g.,𝑛3 ∈Ω 𝑛2 , 𝑛 𝑛 − 1 ∈ Ω 𝑛2
2
◼ 100𝑛 + 5 ∉ Ω 𝑛2
f(n)

𝒇(𝒏) ∈ 𝜴 𝒈(𝒏)

5/30/2023 Nguyen Hai Minh 36

Asymptotic Notations – Big-Theta
 𝜣 𝒈 𝒏 : set of all functions with same order of
growth as 𝑔 𝑛
◼ E.g., 𝑎𝑛2 + 𝑏𝑛 + 𝑐 ∈ Θ 𝑛2 with 𝑎 > 0
◼ 𝑛2 + log 𝑛 ∉ Θ 𝑛2
f(n)

𝒇(𝒏) ∈ 𝜣 𝒈(𝒏)

5/30/2023 Nguyen Hai Minh 37

O-Notation
 Math:
◼For a given function 𝑔 𝑛 , we denote by 𝑂 𝑔 𝑛
(pronounced “big-oh of g of n”) the set of functions

𝑂 𝑔 𝑛 = {𝑓 𝑛 : there exist positive constants 𝑐 and 𝑛𝑜

such that: 0 ≤ 𝑓 𝑛 ≤ 𝑐𝑔 𝑛 for all 𝑛 ≥ 𝑛0 }
◼Explain: 𝑓 is big-O of 𝑔 if there is 𝑐 so that 𝑓 is not
bigger than 𝑐 ∗ 𝑔 when 𝑛 is large enough
 Engineering:
◼Drop low-order terms, ignore leading constants.
◼Ex: 3n3 + 90n2 – 5n + 6046 =O(n3)
5/30/2023 Nguyen Hai Minh 38
O-Notation
o If n is large enough (𝑛 ≥ 𝑛0 ), then 𝑔(𝑛) is the upper
bound of 𝑓(𝑛)
o We write 𝑓 𝑛 ∈ O(𝑔 𝑛 ) to indicate that a function 𝑓 𝑛
is a member of the set O(𝑔 𝑛 )

n0

5/30/2023 Nguyen Hai Minh 39

O-Notation
 O-notation is used to classify algorithms by
how they respond to changes in input size.
 O-notation characterizes functions according to
their growth rates:
◼ different functions with the same growth rate
may be represented using the same O-notation.

5/30/2023 Nguyen Hai Minh 40

 O-Notation – Example
 Prove that 𝒇 𝒏 = 𝟐𝒏𝟐 + 𝟔𝒏 + 𝟏 ∈ 𝑶(𝒏𝟐)
o Let 𝑔 𝑛 = 𝑛2
o We have: 2𝑛2 + 6𝑛 + 1 ≤ 2𝑛2 + 6𝑛2 + 𝑛2 ≤ 9𝑛2 (for
all 𝑛 ≥ 1)
o Thus, as c = 9, 𝑛0 = 1 → 𝑓 𝑛 < 9𝑔 𝑛
o By definition of Big-Oh, 𝑓 𝑛 ∈ 𝑂 𝑛2

Note that you can choose other specific values for

constants 𝑐 and 𝑛0 .
o For example, we can choose 𝑐 = 3, 𝑛0 = 7

5/30/2023 Nguyen Hai Minh 41

 O-Notation – Example
 Prove that 𝒇 𝒏 = 𝒏𝟑 − 𝟏𝟎𝟎𝒏𝟐 ∉ 𝑶(𝒏𝟐)
o If we have 𝑓 𝑛 ∈ 𝑂 𝑛2 , then there would be
positive constants c and 𝑛0 such that
o 𝑛3 − 100𝑛2 ≤ 𝑐𝑛2 (for all 𝑛 ≥ 𝑛0 )
o We divide both sides by 𝑛2, giving 𝑛 − 100 ≤ 𝑐
o Regardless of what value we choose for c, this
inequality does not hold for any value of 𝑛 > 𝑐 +
100

5/30/2023 Nguyen Hai Minh 42

Classification of Algorithms
Order of growth Class name
O(1) Constants
O(log2n) Logarithms
O(n) Linears
O(nlog2n) nlog2n
O(na) Polynomials
O(an), a > 1 Exponentials
O(n!) Fractorials

5/30/2023 Nguyen Hai Minh 43

MATHEMATICAL
ANALYSIS OF
ALGORITHMS
Non-recursive Algorithms
Recursive Algorithms

5/30/2023 Nguyen Hai Minh 44

ANALYSIS OF NON-RECURSIVE ALGORITHMS

1. Decide n – the input size

2. Identify the algorithm’s basic operation (as a rule,
it is located in the innermost loop)
3. Check whether the number of times the basic
operation is executed depends only on n
➢ If it depends on some additional property, specify the
worst-case for Big-Oh
4. Set up a sum expressing the number of times the
algorithm’s basic operation is executed.
5. Find a closed-form formula for the count and
establish its order of growth.
5/30/2023 Nguyen Hai Minh 45
ANALYSIS OF NON-RECURSIVE ALGORITHMS

 Example: Check whether all the elements in a

given array of n elements are distinct.
UniqueElements(A[0..n − 1])
//Determines whether all the elements in a given array are distinct
//Input: An array A[0..n − 1]
//Output: Returns “true” if all the elements in A are distinct
// and “false” otherwise
for i ← 0 to n − 2 do
for j ← i + 1 to n − 1 do
Basic operation
if A[i] = A[j]
return false
return true
5/30/2023 Nguyen Hai Minh 46
ANALYSIS OF RECURSIVE ALGORITHMS

1. Decide n – the input size

2. Identify the algorithm’s basic operation
3. Check whether the number of times the basic
operation is executed depends only on n
1. If it depends on some additional property, specify the
worst-case for Big-Oh
4. Set up a recurrence relation, with an appropriate
initial condition, for the number of times the basic
operation is executed.
5. Solve the recurrence and establish its order of
growth.
5/30/2023 Nguyen Hai Minh 47
ANALYSIS OF RECURSIVE ALGORITHMS

 Example: Compute the factorial function 𝐹(𝑛) = 𝑛! for an

arbitrary non-negative integer 𝑛.

Factorial(n)
//Computes n! recursively
//Input: A nonnegative integer n
//Output: The value of n! Basic operation
if n = 0 return 1
else return Factorial(n – 1) * n

5/30/2023 Nguyen Hai Minh 48

What’s next?
 After today:
◼ Read textbook 1 – section 1.3 (page 85~)
◼ Read textbook 3 – chapter 1 & 2 (page 1~)
◼ Do Homework 1 (work in group of 2 students),
deadline: 23h55, June 10th, 2023
 Next Week:
◼ Quiz 1 (20 mins, from 7:30~)
◼ Lecture 2: Sorting Algorithms

5/30/2023 Nguyen Hai Minh 49