DESIGN AND ANALYSIS OF ALGORITHMS

LECTURE 2
Analysis of Algorithms
Review the Previous Lesson

❑ Some key concepts

▪ Problem; Algorithm; Data Structure; Program.
❑ About Complexity and Analysis of Algorithms
❑ Turing Machine
▪ Description; Structure; and Operation
▪ Formal definition Algorithm
❑ Primitive Recursive Function
▪ Basic primitive recursive functions Computable
▪ Composition; Primitive recursion functions
Outline

❑ The Analysis Framework

❑ Analyze the complexity of Algorithms
❑ Prove the correctness of Algorithms
❑ Exercises

[Anany’s book Chapter 2, page 41]

3
The Analysis Framework

✓ Goals of Algorithm Analysis

✓ Input Data Size and Basic Operation
✓ Orders of Growth
✓ Types of analysis
Goals of Algorithm Analysis

❑ How can we trust the algorithm?

▪ Proving the Correctness.
❑ How to compare the algorithms?
▪ Assessing the Effectiveness.
Effectiveness: Two kinds of algorithm efficiency
▪ Time efficiency - how fast the algorithm runs?
 Time complexity – Độ phức tạp thời gian.
▪ Space efficiency - how much extra memory it uses?
 Space complexity – Độ phức tạp không gian.
Goals of Algorithm Analysis

❑ In theoretical analysis of algorithms, the complexity

is commonly estimated in the asymptotic sense, i.e.,
to estimate the complexity as a function of arbitrarily
large input.
Trong phân tích lý thuyết thuật toán, độ phức tạp thường
được ước lượng theo nghĩa tiệm cận, tức là ước tính độ
phức tạp như một hàm đối với dữ liệu đầu vào có kích
thước lớn tùy ý.
Goals of Algorithm Analysis
❑ Theoretical Analysis of Time Complexity:
▪ Time complexity is determined by the number of repetitions
of the basic operations as a function of the input data size.

n: Input data size

T(n)  cop C(n)

T(n): Running
time C(n): Number of times
basic operation is executed
cop: Execution time for
basic operation
Input Data Size and Basic Operation
❑ Input Data Size: number of elements or value of input.
❑ Basic Operation: compare, arithmetic operation, element
accesses...

Problem Input size Basic operation

Search for key in a list Number of items in list n Key comparison

Multiply two matrices Dimensions of matrices Floating-point multiplication

Compute an Value of n Floating-point multiplication

Size of graph (Number of Visiting a vertex or traversing

Find a path on a graph
vertices and edges) an edge
Goals of Algorithm Analysis
❑ Theoretical Analysis of Time Complexity:
▪ Example with Insertion Sort
Instruction Running Time
InsertionSort(A, n) {
for i = 2 to n { c1n
key = A[i] c2(n-1)
j = i - 1 c3(n-1)
while (j > 0) and (A[j] > key) { c4T
A[j+1] = A[j] c5(T-(n-1))
j = j - 1 c6(T-(n-1))
}
A[j+1] = key c7(n-1)
}
}
T = t2 + t3 + … + tn where ti is the number of times the while loop condition
is tested for value j at step i.
Goals of Algorithm Analysis
❑ Theoretical Analysis of Time Complexity:
▪ Example with Insertion Sort
→ T(n) = c1n+c2(n-1)+c3(n-1) + c4T + c5(T-(n-1)) + c6(T-(n-1)) + c7(n-1)
= c8T + c9n + c10, where T = t2 + t3 + … + tn
Best Case: Array already sorted → Loop condition fails immediately → ti = 1, i
→ T (n) = c8n + c9 n + c10 = an + b, (Linear).
Worst Case: Array reverse sorted → Loop runs fully for each i → ti = i
n
n(n + 1)
→ T (n) = c8  i + c9 n + c10 = c8 + c9 n + c10 = an 2 + bn + c, (Quadratic)
i =2 2
Average Case: Assume key is inserted in the middle → ti  i / 2.
n
i 1 n(n + 1)
→ T (n)  c8  + c9 n + c10 = c8 + c9 n + c10 = an 2 + bn + c,(Quadratic)
i =2 2 2 2
 Orders of Growth
❑ The Running Time Formula T (n)  cop .C (n)
❑ Two factors affect the growth of T (n)
▪ cop: Cost per an operation (Hardware/Language dependent)
▪ C(n): Number of operations (Algorithm dependent)
Better Hardware Larger Input
Effect of doubling hardware speed Impact of doubling input data size (n→2n)?
(cop→1/2cop)?
Running time decreases by half Depends on the Algorithm!
(Hardware gives constant - If C(n) ~ n (Linear): Time doubles (2x).
improvement).
- If C(n) ~ n2 (Quadratic): Time quadruples (4x)
- If C(n) ~ n2 (Cubic): Time increases (8x)

Focus on C (n) – the Order of Growth – to evaluate algorithm efficiency.

Orders of Growth

❑ Value of several functions important for analysis of algorithms

[Anany’s book, page 46]

Orders of Growth

❑ Common Time Complexity Classes

Orders of Growth

❑ The Power of Exponential Growth

Volume of a grain: 2mm3, Total V=265 mm3 ≈ 12.000 Giza pyramids

[Link]
Types of Analysis
❑ Best-case, Average-case, Worst-case
For some algorithms the efficiency depends on the type of input:
▪ Worst case: W(n) – maximum over inputs of size n
▪ Best case: B(n) – minimum over inputs of size n
▪ Average case: A(n) – “average” over inputs of size n
• Number of times the basic operation is executed on a typical input
• NOT the average of the worst and best cases
• Average-case analysis depends on assumptions about the probability
distribution of inputs.
Analyze the complexity of Algorithm

✓ Asymptotic Notations
✓ Establishing rate of growth relation
Asymptotic Notations

❑ Asymptotic notations are syntax for presenting the

upper and lower bounds of algorithm complexity.
▪ Best case but What is the lower bound?
▪ Worst case but What is the upper bound?
▪ Average case but What is the interval bound?
❑ A method to compare functions that ignores constant
factors and small input sizes.
❑ Three main Asymptotic notations:
• O - Big-oh
•  - Big-omega
•  - Big-theta
 Asymptotic Notations

❑ O - Big-oh (đọc là O lớn – Tiệm cận trên)

▪ Definition:
f(n) = O(g(n)) if exist c,n0 such
f(n)  c.g(n) for all n  n0
▪ Meaning:
f(n) grows at most as fast as g(n)

O notation: Worst-case upper bound.

Interested in the smallest valid bound.
 Asymptotic Notations

❑  - Big-omega (đọc là Omega lớn – tiệm cận dưới)

▪ Definition:
f(n) = (g(n)) if exist c,n0 such
f(n)  c.g(n) for all n  n0
▪ Meaning:
f(n) grows at least as fast as g(n)

 notation: Best-case lower bound.

Interested in the largest valid bound.
 Asymptotic Notations

❑  - Big-theta (đọc là Theta lớn - tiệm cận chặt)

▪ Definition:
f(n) = (g(n)) if exist c1,c2,n0 such
c1.g(n)  f(n)  c2.g(n) for all n  n0
▪ Meaning:
f(n) grows at the same rate as g(n)

 notation: Average-case tight bound.

Interested in the exact order of growth.
Asymptotic Notations

❑ Example
- Time complexity of Insertion Sort is O(n2), isn’t it?
f(n)= an2+bn+c = O(n2)
- Prove:
f(n) = an2 + bn + c
 (a + b + c)n2 + (a + b + c)n + (a + b + c)
 3(a + b + c)n2 with n  1
Choose c’ = 3(a + b + c), n0 = 1  f(n)  c’.n2
or f(n) = O(n2) ◼
- Is f(n)= an2+bn+c = O(n3)? - Yes, but need the smallest.

- More examples in Anany’s book page 53-55

Useful Property of the Asymptotic Notations

❑ Theorem:

▪ Prove: See [Anany’s book page 56].

▪ Property useful in analyzing algorithms that comprise two
consecutively executed parts.
Useful Property of the Asymptotic Notations

❑ Other properties of asymptotic relationship:

Transitivity:
f(n) = (g(n)) & g(n) = (h(n))  f(n) = (h(n))
f(n) = O(g(n)) & g(n) = O(h(n))  f(n) = O(h(n))
f(n) = (g(n)) & g(n) = (h(n))  f(n) = (h(n))
Reflexivity:
f(n) = (f(n))
f(n) = O(f(n))
f(n) = (f(n))
Symmetry and Transpose Symmetry:
f(n)= (g(n))  g(n)= (f(n))
f(n)=O(g(n))  g(n)= Ω(f(n))
Establishing rate of growth relation

❑ Establishing rate of growth relation

▪ Given 2 complexity functions f(n) và g(n). Lets determine
f(n) = *(g(n)) with * is O or  or ?
❑ Three methods
Using mathematical definition:
Find constants c, n0 satisfy the conditions
Using inductive proof:
Example: log n= O(n) or log(n)  c.n
Base: n = 1 => 0 < 1 - is true
Inductive step:
Assume log(n)  n when n>1
Then log(n+1)  log (n+n) = log (2n) = log n + 1  n+1 ◼
Using limits (when n →)
Establishing rate of growth relation

❑ Using limits (when n → )

0 ⇒ 𝑓(𝑛) = O(𝑔(𝑛))
𝑓(𝑛) ∞ ⇒ 𝑓(𝑛) = Ω(𝑔(𝑛))
lim =
𝑛→∞ 𝑔(𝑛) 𝑐𝑜𝑛𝑠𝑡 ⇒ 𝑓(𝑛) = Θ(𝑔(𝑛))
𝑢𝑛𝑘𝑛𝑜𝑤 ⇒ no relation
Example:
Given f (n) = n n and g (n) = n 2 − n
f ( n) n n n
lim = lim 2 = lim =0
n → g ( n) n→ n − n n→ n − 1

 f (n) = O( g (n))

More examples [Anany’s book page 57]

Establishing rate of growth relation

❑ Calculus techniques for computing limits

▪ L’Hôpital’s rule

▪ Stirling’s formula
Proving Algorithm Correctness

✓ Algorithm’s correctness
✓ Correctness of Recursive algorithm
✓ Correctness of Iterative algorithm
Correctness of Algorithms
❑ How do we know that an algorithm works?
The answer leads to the need for checking correctness.

❑ Methods for establishing algorithm correctness

▪ Testing: Try the algorithm on sample inputs.
Testing may fail to reveal subtle or obscure bugs.
Using testing alone is insufficient.
▪ Correctness proof: Mathematical proof of correctness
Correctness proofs may also contain errors.
A combination of testing and correctness proof provides
greater confidence in algorithm correctness.
Correctness of Recursive algorithms
❑ Recursive algorithm
A recursive algorithm is an algorithm that calls itself on smaller
(or simpler) instances of the same problem.

❑ Proving correctness by induction:

Prove by mathematical induction on the “size” of the problem:
▪ Base case: The base case of the recursion is correct.
▪ Inductive hypothesis: Assume that the recursive call works correctly
for input size n.
▪ General case: Using the hypothesis, prove that the algorithm works
correctly for size n+1.
▪ Termination:Since the recursion eventually reaches the base case,
the algorithm terminates.
Correctness of Recursive algorithms
❑ Example
▪ Recursive algorithm find maximum of a list:
Maximum(A,n)  //Find the maximum
if (n==1) return (A1)
else return(max(Maximum(A,n-1),An)
End.
▪ Claim: maximum(n) returns max{A1,A2,…,An} for all n ≥ 1
▪ Proof by induction on n:
• Base case: n = 1, maximum(A,n) returns A1 as claimed
• Inductive assumption: maximum(A,n) returns max {A1,A2,…,An}
• General case: Maximum(A,n+1) returns max(Maximum(A,n),An+1)
= max(A1,…, An, An+1)
Correctness of Iterative algorithms
❑ Iterative algorithm
▪ A non-recursive algorithm that uses one or more loops.
▪ Prove the correctness by loop invariant
❑ Loop invariant
▪ A logical statement about program variables that is true before and after
each iteration of the loop. - Biểu thức logic luôn đúng ở mỗi lần lặp
▪ Loop invariants are used to prove that an algorithm terminates and
produces correct results – Dùng để chứng minh thuật toán dừng và cho
kết quả đúng.
▪ For algorithms with nested loops, the loop invariant is usually established
starting from the innermost loop. – Với các vòng lặp lồng nhau sẽ bắt
đầu từ vòng lặp trong cùng.
Correctness of Iterative algorithms
❑ Properties of loop invariant
▪ Initialization (khởi tạo): The loop invariant is true before the first
iteration of the loop.

▪ Maintenance (duy trì): If the loop invariant is true at the beginning of

an iteration, it remains true at the beginning of the next iteration.

▪ Termination (kết thúc): The loop eventually terminates.

When the loop terminates, the loop invariant, together with the
termination condition, implies the correctness of the loop and
the algorithm.
Correctness of Iterative algorithms
❑ Example: Non-recursive algorithm find maximum of a list:
Maximum(A,n)  //Find the maximum of the list has n items
m = A1
for (i=2;i<=n;i++) if (m<Ai) m = Ai
return (m)
End.
Loop invariant: mj = max(A1,…,Aj)
▪ Initialization: m1 = A1 = max(A1) - is true
▪ Maintenance: if mj= max(A1,…,Aj), have mj+1= max(mj,Aj+1)= max(A1,…,Aj+1)
▪ Termination: when i=n+1, after t iterations (t= n+1-2+1=n)
mt = max(A1,…At) = max(A1,…An)
Because the loop invariant is maintained and the loop terminates, the
Maximum algorithm is correct.
See more [Rodney R. Howell, Algorithm: a Top-Down Approach, Chapter 2]
Exercises

❑ Measuring input size and orders of growth.

❑ Establishing growth-rate relationships between functions.
❑ Designing and analyzing a sorting algorithm.
❑ Further details are provided in Hw2_AlgorithmAnalysis.