Algorithm Efficiency

Contents
o A review on algorithm

o Analysis and Big-O notation

o Algorithm efficiency

fit@hcmus | DSA | 2024 2

1
 A review on algorithm

fit@hcmus | DSA | 2024 3

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

fit@hcmus | DSA | 2024 4

2
 Algorithm
o Give some examples of algorithms.

fit@hcmus | DSA | 2024 5

An Example
o Input: No
o Output: what do you think about the output?

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

o Step 2.
• Assign i = i + 1
• Assign sum = sum + i
o Step 3. Compare i with 10
• if i < 10, back to step 2.
• otherwise, if i ≥ 10, go to step 4.
o Step 4. return sum

fit@hcmus | DSA | 2024 6

3
 Characteristics of Algorithms
o Finiteness
For any input, the algorithm must terminate after a finite number of steps.
o Correctness
Always correct. Give the same result for different run time.
o Definiteness
All steps of the algorithm must be precisely defined.
o Effectiveness
It must be possible to perform each step of the algorithm correctly and in a
finite amount of time.

fit@hcmus | DSA | 2024 7

Characteristics of Algorithms

fit@hcmus | DSA | 2024 8

4
 Algorithm Efficiency
o 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.

fit@hcmus | DSA | 2024 9

Measuring Efficiency of Algorithms

o 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?

fit@hcmus | DSA | 2024 10

10

5
 Measuring Efficiency of Algorithms
o Difficulties with comparing programs instead of algorithms
• How are the algorithms coded?
• What computer should you use?
• What data should the programs use?

fit@hcmus | DSA | 2024 11

11

Measuring Efficiency of Algorithms

o Comparison of algorithms should focus on significant differences in
efficiency

o Employ mathematical techniques that analyze algorithms

independently of specific implementations, computers, or data.

fit@hcmus | DSA | 2024 12

12

6
 Execution Time of Algorithm
o Time complexity is measured by counting the primitive
operations for the computation that the algorithm needs to
perform.
• Comparisons
• Assignments
o Derive an algorithm’s time requirement as a function of the
problem size
• Algorithm A requires n2/ 5 time unit to solve a problem of size n.
• Algorithm B requires 5 x n time unit to solve a problem of size n.

fit@hcmus | DSA | 2024 13

13

Execution Time of Algorithm

o Traversal of linked nodes – example:

• Assignment: a time units.

• Comparison: c time units.
• Write: w time units.
o Displaying data in linked chain of n nodes requires time proportional to n

fit@hcmus | DSA | 2024 14

14

7
 Execution Time of Algorithm
o Nested loops

• Task T requires t time units.

fit@hcmus | DSA | 2024 15

15

Previous Example
o Step 1. Assign sum = 0. Assign i = 0.
o Step 2.
• Assign i = i + 1
• Assign sum = sum + i
o Step 3. Compare i with 10
• if i < 10, back to step 2.
• otherwise, if i ≥ 10, go to step 4.
o Step 4. Return sum
How many
• Assignments?22
• Comparisons? 10
fit@hcmus | DSA | 2024 16

16

8
 Another Example
o Step 1. Assign sum = 0. Assign i = 0.
o Step 2.
• Assign i = i + 1
• Assign sum = sum + i
o Step 3. Compare i with n
• if i < n, back to step 2.
• otherwise, if i ≥ n, go to step 4.
o Step 4. Return sum
How many
• Assignments?
• Comparisons?
fit@hcmus | DSA | 2024 17

17

Algorithm Growth Rates

o Measure algorithm’s time requirement as a function of problem
size
o Compare algorithm efficiencies for large problems
o Look only at significant differences.

fit@hcmus | DSA | 2024 18

18

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

fit@hcmus | DSA | 2024 19

19

Analysis and Big O Notation

fit@hcmus | DSA | 2024 20

20

10
 Big O Notation
o Definition:
• Algorithm A is order f ( n )
• Denoted 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 .

fit@hcmus | DSA | 2024 21

21

Example
o An algorithm requires n2 - 3  n + 10 (time units). What is the order
of algorithm?
• Hint: Find the values k va n0.

fit@hcmus | DSA | 2024 22

22

11
 Example

The graphs of 3  n2 and n2 - 3  n + 10

fit@hcmus | DSA | 2024 23

23

Another Example
o How about the order of an algorithm requiring
(n + 1)  (a + c) + n x w
time units?

fit@hcmus | DSA | 2024 24

24

12
 Another Example
o Another algorithm requires n2 + 3  n + 2 time units. What is
the order of this algorithm?

fit@hcmus | DSA | 2024 25

25

Common Growth-Rate Functions

o f(n) =
• 1: Constant
• log2n: Logarithmic
• n: Linear
• n  log2n: Linearithmic
• n2: Quadratic
• n3: Cubic
• 2n: Exponential

fit@hcmus | DSA | 2024 26

26

13
 Common Growth-Rate Functions
o Order of growth of some common functions

fit@hcmus | DSA | 2024 27

27

Common Growth-Rate Functions

o A comparison of growth-rate functions in tabular form

fit@hcmus | DSA | 2024 28

28

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

fit@hcmus | DSA | 2024 29

29

Properties of Growth-Rate Functions

o Ignore low-order terms
o Ignore a multiplicative constant in the high-order term
o O(f(n)) + O(g(n)) = O(f(n) + g(n))

fit@hcmus | DSA | 2024 30

30

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

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

fit@hcmus | DSA | 2024 31

31

Some Useful Results

o 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)) )

o Multiplication Function:
• If f1(n) is O(g1(n)) and f2(n) is O(g2(n))
• Then f1(n) x f2(n) is O( g1(n) x g2(n) )

fit@hcmus | DSA | 2024 32

32

16
 Quiz
Are these functions of order O(x)?
a) f(x) = 10
b) f(x) = 3x + 7
c) f(x) = 2x2 + 2

fit@hcmus | DSA | 2024 33

33

Quiz
What are the order of the following functions?
• 𝑓 𝑛 = 2 + 𝑛 3 + log2𝑛
𝑛
• 𝑓 𝑛 = 11 log2𝑛 + 2 – 3542
• 𝑓 𝑛 = 𝑛 3 + 𝑛 – 7𝑛
• 𝑓 𝑛 = log 2 (𝑛2 ) + 𝑛

fit@hcmus | DSA | 2024 34

34

17
 Quiz
o What are the order of the following functions?
• 𝑓 𝑛 = 3𝑛 + 𝑛5
• 𝑓 𝑛 = 5𝑛3 + 100𝑛2 + 200
• 𝑓 𝑛 = 𝑛 log 𝑛 + 500𝑛
• 𝑓 𝑛 = 𝑛 + 𝑙𝑜𝑔 𝑛
• 𝑓 𝑛 = 𝑛! + 2𝑛

fit@hcmus | DSA | 2024 35

35

Notes
o Use like this:
• f(x) is O(g(x)), or
• f(x) is of order g(x), or
• f(x) has order g(x)

fit@hcmus | DSA | 2024 36

36

18
 Algorithm Efficiency

fit@hcmus | DSA | 2024 37

37

Algorithm Efficiency
o Best case scenario

o Worst case scenario

o Average case scenario

fit@hcmus | DSA | 2024 38

38

19
 An Algorithm to Analyze
o Input:
o Output:

o Step 1. Set the first integer the temporary maximum

value (temp_max).
o Step 2. Compare the current value with the temp_max.
• If it is greater than, assign the current value to temp_max.
o Step 3. If there is other integer in the list, move to
next value. Back to step 2.
o Step 4. If there is no more integer in the list, stop.
o Step 5. return temp_max (the maximum value of the list).

fit@hcmus | DSA | 2024 39

39

Another Algorithm to Analyze

o Input:
o Output:

o Step 1. Assign i = 0
o Step 2. While i < n and x  ai, increase i by 1.
while (i < n and x  ai)
i = i + 1
o Step 3.
• If i < n, return i.
• Otherwise (i >= n), return -1 to tell that x does not exist
in list a.

fit@hcmus | DSA | 2024 40

40

20
 Another Algorithm to Analyze
o Use comparisons for counting.

o Worst case:
• When it occurs?
• How many operations?

o Best case:
• When it occurs?
• How many operations?

fit@hcmus | DSA | 2024 41

41

Another Algorithm to Analyze

o Use comparisons for counting.

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

fit@hcmus | DSA | 2024 42

42

21
 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.
fit@hcmus | DSA | 2024 43

43

Analysis of Algorithms

fit@hcmus | DSA | 2024 44

44

22
 Analysis of Algorithms

fit@hcmus | DSA | 2024 45

45

Keeping Your Perspective

o If problem size always small, ignore an algorithm’s efficiency
o Weigh trade-offs between algorithm’s time and memory
requirements
o Compare algorithms for both style and efficiency

fit@hcmus | DSA | 2024 50

50

23
 Exercises

fit@hcmus | DSA | 2024 51

51

Exercise
o 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!
o 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;
}

fit@hcmus | DSA | 2024 52

52

24
 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];
}

fit@hcmus | DSA | 2024 53

53

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

fit@hcmus | DSA | 2024 54

54

25
 Exercise
o 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++;

fit@hcmus | DSA | 2024 55

55

Exercise
o 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++;

fit@hcmus | DSA | 2024 56

56

26
 Questions and Answers

fit@hcmus | DSA | 2024 57

57

27