University of Science – VNU-HCM

Faculty of Information Technology

CSC10004 – Data Structures and Algorithms

Session 02 -
Algorithm Efficiency
Instructor:
Dr. LE Thanh Tung

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 1

Content

1 A review on algorithm
2 Analysis and Big-O notation
3 Algorithm efficiency

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 2

 A review on
Algorithm

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 3

Algorithm
▪ What is Algorithm?
▪ A strictly defined finite sequence of well-defined steps (statements,
often called instructions or commands)
▪ that provides the solution to a problem.

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 4

Algorithm
▪ Example:
▪ Problem: a child wonder
whether they can go to the
movies in case of having a
homework today.

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 5

Algorithm
▪ Why should we study algorithm?
▪ To understand the basic idea of the problem.
▪ To find an approach to solve the problem.
▪ To improve the efficiency of existing techniques.
▪ To understand the basic principles of designing the algorithms.
▪ To break down problems and conceptualize solutions in terms of
discrete steps

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 6

Algorithm
▪ Algorithm’s Characteristics:

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 7

Algorithm
▪ Algorithm’s Characteristics:
▪ Finiteness: for any input, the algorithm must terminate after a finite
number of steps.
▪ Correctness: always correct. Give the same result for different run
time.
▪ Definiteness: all steps of the algorithm must be precisely defined.
▪ Effectiveness: It must be possible to perform each step of the
algorithm correctly and in a finite amount of time.

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 8

Types of Algorithm

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 9

Algorithm
▪ What kind of problems are solved by Algorithm?
▪ Sorting
▪ Searching
▪ String matching
▪ Graph problems
▪ Combinatorial problems
▪ Geometric problems
▪ Numerical problems

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 10

Algorithm Analysis
▪ The two factors of Algorithm Efficiency are:

▪ Time Factor: Time is measured by counting the number of

key operations.

▪ Space Factor: Space is measured by counting the maximum

memory space required by the algorithm.

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 11

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

→ Concentrate on time efficiency, but analytical framework in

this course is applicable to analyzing space efficiency as well

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 12

Measuring Efficiency of Algorithms
▪ Can we compare two algorithms (in time factor) like this?
▪ Implement those algorithms (into programs)
▪ Calculate the execution time of those programs
▪ Compare those two values of time measurement.

Is it fair in this measuring process?

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 13

Measuring Efficiency of Algorithms
▪ Comparison of algorithms should focus on significant differences in
efficiency
▪ Difficulties with comparing programs instead of algorithms
▪ How are the algorithms coded?
▪ What computer should you use?
▪ What data should the programs use?

→ Employ mathematical techniques that analyze algorithms

independently of specific implementations, computers, or data

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 14

Measuring Efficiency of Algorithms
▪ Time complexity is measured by counting the primitive operations for
the computation that the algorithm needs to perform.
▪ Key operation is to contribute the most to the total running time of an
algorithm
▪ Comparisons
▪ Assignments
▪ Derive an algorithm’s time requirement as a function of the problem
size

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 15

Problem 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

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 16

Problem 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

▪ Spell-checking a document

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 17

 Time Complexity
▪ Traversal of linked nodes – example:
void printList(Node* pHead){
Node* pCur = pHead; 1 assignment
while (pCur != nullptr){ n + 1 comparisions
cout << pCur->key << endl; n + 1 writes
pCur = pCur->next; n + 1 assignments
}
}
▪ Assignment: a time units. Comparison: c time units.
▪ Write: w time units.
▪ Displaying data in linked list of n nodes requires time proportional to n

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 18

 Time Complexity
▪ Nested loops

▪ Task T requires t times units

▪ How to find the relationship between t times and the problem sizes n

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 19

 Example
Step 1. Assign sum = 0. Assign i = 0.

Step 2.
Assign i = i + 1
Assign sum = sum + i How many
Assignments?
Comparisons?
Step 3. Compare i with 10
if i < 10, back to step 2.
otherwise, if i ≥ 10, go to step 4.

Step 4. Return sum

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 20
 Example
Step 1. Assign sum = 0. Assign i = 0.

Step 2.
Assign i = i + 1
Assign sum = sum + i How many
Assignments?
Comparisons?
Step 3. Compare i with n
if i < n, back to step 2.
otherwise, if i ≥ n, go to step 4.

Step 4. Return sum

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 21
 Example
▪ Sum of n integer S(n) = 0 + 1 + 2 + ... + n - 1

int sum = 0;
for (int i = 0; i < n; i++) Assignment: 2n + 2
sum = sum + i;

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

▪ Running Time: T(n) = 3n + 3

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 22
 Algorithm Growth Rates
▪ Measure algorithm’s time requirement as a function of
problem size
▪ Compare algorithm efficiencies for large problems
▪ Look only at significant differences.

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 23

 Analysis &
Big O Notation

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 24

 Algorithm Growth Rates
▪ Time requirements as a function of the problem size n

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 25

 Big O Notation
▪ Definition:
▪ Algorithm A with time unit function g(n) is order f(n)
▪ Denoted g(n)is O(f(n))
▪ If constants k and n0 exist such that A requires no more than
k  f(n) time units to solve a problem of size n ≥ n0.
▪ It means that for all n ≥ n0, g(n)  c • f(n)

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 26

Big O Notation

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 27

 Big O Notation
▪ An algorithm requires g(n)= n2 - 3n + 10 (time units).
▪ What is the order of algorithm?
▪ Hint: Find the values k and n0.

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 28

 Big O Notation

▪ With c = 3 and n0 = 2, g(n) = O(n2)

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 29
 Big O Notation
▪ Another algorithm requires n2 + 3n + 10 time units. What is
the order of this algorithm?

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 30

 Big O Notation
▪ How about the order of an algorithm requiring
(n + 1)  (a + c) + n  w
time units?
Where n is the problem size

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 31

Common Growth-Rate Functions
▪ f(n) =
▪ 1: Constant
▪ log2n: Logarithmic
▪ n: Linear
▪ nlog2n: Linearithmic
▪ n2: Quadratic
▪ n3: Cubic
▪ 2n: Exponential

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 32

Common Growth-Rate Functions
▪ Order of growth of some common functions

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 33

Common Growth-Rate Functions
▪ A comparison of growth-rate functions in tabular form

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 34

Common Growth-Rate Functions
▪ A comparison of growth-rate functions in graphical form

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 35

Properties of Growth-Rate Functions
▪ Ignore low-order terms
O(n3 + 4n2 + 3n) == O(n3)
▪ Ignore a multiplicative constant in the high-order term
O(5n3) == O(n3)
▪ Can combine growth rate functions
O(f(n)) + O(g(n)) = O(f(n) + g(n))

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 36

Some Useful Results
▪ Constant Multiplication:
If f(n) is O(g(n))
then c*f(n) is O(g(n)), where c is a constant.

▪ Polynomial Function:
f(x) = anxn + an-1xn-1 + … + a1x + a0 is O(xn)

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 37

Some Useful Results
▪ Summation Function:
▪ If f1(n) is O(g1(n)) and f2(n) is O(g2(n))
▪ Then f1(n) + f2(n) is O(max(g1(n),g2(n)))

▪ Multiplication Function:
▪ If f1(n) is O(g1(n)) and f2(n) is O(g2(n))
▪ Then f1(n)f2(n) is O(g1(n)g2(n))

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 38

Note
▪ Use like this:
▪ f(x) is O(g(x)), or
▪ f(x) is of order g(x), or
▪ f(x) has order g(x)

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 39

Quiz
▪ Are these functions of order O(x)?
▪ f(x) = 10
▪ f(x) = 3x + 7
▪ f(x) = 2x2 + 2

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 40

Quiz
▪ Give the order of growth (as a function of n) of
the running time of the following function?
▪ f(n) = (2 + n) * (3 + log2n)
▪ f(n) = 11 * log2n + n/2 – 3542
▪ f(n) = n * (3 + n) – 7 * n
▪ f(n) = log2(n2) + n

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 41

Quiz
▪ Give the order of growth (as a function of n) of the running time of
the following function?
▪ f(n) = (2 + n) * (3 + log2n)
▪ f(n) = 11 * log2n + n/2 – 3542
▪ f(n) = n * (3 + n) – 7 * n
▪ f(n) = log2(n2) + n

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 42

 Algorithm Efficiency

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 43

Algorithm Efficiency
▪ Best case scenario

▪ Worst case scenario

▪ Average case scenario

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 44

Example
▪ Input: ???
▪ Output: ???
▪ Step 1. Set the first integer the temporary maximum value (temp_max).
▪ Step 2. Compare the current value with the temp_max.
▪ If it is greater than, assign the current value to temp_max.
▪ Step 3. If there is other integer in the list, move to next value. Back to
step 2.
▪ Step 4. If there is no more integer in the list, stop.
▪ Step 5. return temp_max (the maximum value of the list).
Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 45
Example
▪ Input:
▪ Output:
▪ Step 1. Assign i = 0
▪ Step 2. while (i < n and x  ai)
i = i + 1
▪ Step 3.
▪ if i < n, return i
▪ Otherwise (i ≥ n), return -1 to tell that x does not
exist in list a.

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 46

Example
▪ Use comparisons for counting.

▪ Worst case:
▪ When it occurs?
▪ How many operations?

▪ Best case:
▪ When it occurs?
▪ How many operations?
Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 47
Algorithm Efficiency
▪ Use comparisons for counting.

▪ Average case:
▪ If x is found at position ith, the number of comparisons is
2i + 1
▪ The average number of comparisons is:
n(n + 1)
2 +n
3 + 5 + 7 + .. + (2n + 1) 2(1 + 2 + 3 + ... + n) + n 2
= = = n+2
n n n

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 48

Analysis of algorithms
▪ Decide n – the input size
▪ Identify the algorithm’s basic operation (as a rule, it is in the innermost
loop)
▪ 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
▪ Set up a sum expressing the number of times the algorithm’s basic
operation is executed.
▪ Find a closed-form formula for the count and establish its order of
growth.
Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 49
Analysis of algorithms

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 50

Analysis of algorithms

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 51

 Exercise

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 52

Exercise
Propose an algorithm to calculate the value of S defined below. What order
does the algorithm have?

1 1 1
S = 1 + + + ... +
2 6 n!

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 53

Exercise
How many comparisons, assignments are there in the following code
fragment with the size n?
sum = 0;
for (i = 0; i < n; i++)
{
std::cin >> x;
sum = sum + x;
}

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 54

Exercise
How many assignments are there in the following code fragment
with the size n?
for (i = 0; i < n ; i++)
for (j = 0; j < n; j++){
C[i][j] = 0;
for (k = 0; k < n; k++)
C[i][j] = C[i][j] + A[i][k] * B[k][j];
}

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 55

Exercise
Give the order of growth (as a function of n) of the running time
of the following code fragment:

int sum = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < n; j++)
sum++;

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 56

Exercise
Give the order of growth (as a function of N) of the running time
of the following code fragment:
int sum = 0;
for (int i = 1; i < N; i *= 2)
for (int j = 0; j < N; j++)
sum++;

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 57

Exercise
Give the order of growth (as a function of N) of the running time
of the following code fragment:

int sum = 0;
for (int i = 1; i < n; i *= 2)
for (int j = 0; j < i; j++)
sum++;

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 58

Exercise

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 59

Exercise
Give the order of growth (as a function of n) of the running time
of the following code fragment:

int sum = 0;
for (int k = 1; k < n; k = k*2)
for (int i = 0; i < k; i++)
sum++;

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 60

Geometric Sequence
▪ A geometric sequence, or geometric progression, is a sequence of
numbers where each successive number is the product of the previous
number and some constant r
𝑎𝑛 = 𝑟𝑎𝑛 −1
𝑎𝑛
▪ common ratio: 𝑟 =
𝑎𝑛 −1

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 61

Geometric Series
▪ A geometric series is the sum of the terms of a geometric sequence
▪ Consider the sequence as follows:

▪ the formula for the n-th partial sum of a geometric sequence

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 62

 Exercise
What is the goal of the following code and give the order of growth
function of its running time
void mystery(int*& arr, int n, int a[], int k) {
arr = new int[n]{0};
for (int i = 0; i < k; i++) arr[i] = a[i];
for (int i = k; i < n; ++i) {
int j = 0;
while (j < k){
*(arr + i) += *(arr + i - j - 1);
j++;
}
}
}
Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 63
 Exercise
▪ Hint: this is the main function for the above fragment of code
int main() {
int *arr = NULL;
int start[3] = {-2, 0, 3};
mystery(arr, 7, start, 3);
for (int i = 0; i < 7; i++)
std::cout << arr[i] << std::endl;
if (arr != NULL) delete[] arr;
return 0;
}

▪ What is the output of the function

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 64

 THANK YOU
for YOUR ATTENTION

Dr. LE Thanh Tung CSC10004 – Data Structures and Algorithms Page 65