112-2 (Spring 2024) Semester

Algorithms

Lecture 2: Growth of Functions

Slides
Shao-Hua Sun (孫紹華)
Assistant Professor in Electrical Engineering,
National Taiwan University

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 1 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 Disclaimer
• This is an EMI (English as a Medium of Instruction) course
• I will be teaching in English
• You will be asking questions in English
• Algorithm is not my expertise
• I might not be able to answer all your questions
• I am not particularly familiar with the textbook
• Breaks
• We might not be taking breaks on time due to my poor time management skill
• My slides are largely based on
• The textbook
• The slides from Prof. Yao-Wen Chang (張耀⽂), Prof. Iris Hui-Ru Jiang (江蕙如),

Prof. James Chien-Mo Li (李建模), and Prof. Ho-Lin Chen (陳和麟)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 2 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 On Algorithm

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 3 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 On Algorithm
Algorithm
• A well-de ned procedure for transforming some input to a desired output

Major concerns
• Correctness: Does it halt? Is it correct?
• E ciency: Time complexity? Space complexity?
• Worst case? Average case? Best case?

Better algorithms
• How: Faster algorithms? Algorithms with less space requirement?
• Optimality: Prove that an algorithm is best possible/optimal? Establish a
lower bound?

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 4 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
ffi
fi
 Example: Sorting
Input: a sequence of n numbers <a1, a2, ..., an>.
Output: a permutation <a1', a2', ..., an'> such that a1' ≤ a2’ ≤ … ≤ an'.

Input: [8, 6, 9, 7, 5, 2, 3]
Output: [2, 3, 5, 6, 7, 8, 9]

Can we nd correct and e cient sorting algorithms?

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 5 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
ffi
 Insertion Sort

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 6 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 Incremental Approach: Insertion Sort
Sorted Unsorted

Insert

Sorted Unsorted

Intuition: How do you sort poker cards?

1. Keep left cards sorted, right cards unsorted
2. Each time insert a new card to left cards, in sorted order
3. Repeat until all cards inserted

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 7 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 Insertion Sort
InsertionSort(A) 1 j=2 5 2 4 6 1 3
1. for j = 2 to A.length
2. key = A[j]
// insert A[j] into the sorted
sequence A[1, …, j-1] 2 j=3 2 5 4 6 1 3
3. i = j-1
4. while i > 0 and A[i] > key
5. A[i+1] = A[i] // slide right 3 j=4 2 4 5 6 1 3
6. i = i-1
7. A[i+1] = key // insert
8. return A
4 j=5 2 4 5 6 1 3

5 j=6 1 2 4 5 6 3

Done! 1 2 3 4 5 6

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 8 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 Insertion Sort - Practice
InsertionSort(A) 1 j=2 4 3 5 1 6 2
1. for j = 2 to A.length
2. key = A[j]
// insert A[j] into the sorted
sequence A[1, …, j-1] 2 j=3
3. i = j-1
4. while i > 0 and A[i] > key
5. A[i+1] = A[i] // slide right 3 j=4
6. i = i-1
7. A[i+1] = key // insert
8. return A
4 j=5

5 j=6

Done!

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 9 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 Loop Invariant for Proving Correctness
InsertionSort(A)
1. for j = 2 to A.length
2. key = A[j]
// insert A[j] into the sorted Loop invariant
sequence A[1, …, j-1] • subarray A[1, …, j-1] consists of the
3. i = j-1
4. while i > 0 and A[i] > key elements originally in A[1, …, j-1] but
5. A[i+1] = A[i] // slide right
6. i = i-1
in sorted order
7. A[i+1] = key // insert
8. return A

We can use the loop invariant property to prove the correctness

• Initialization: True before the 1st iteration
• Maintenance: If it is true before an iteration, it remains true before the next iteration
• Termination: When the loop terminates, the invariant leads to the correctness of the algorithm
→ Mathematical induction

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 10 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 Loop Invariant of Insertion Sort
Loop invariant: subarray A[1..j-1] consists of the elements originally in A[1..j-1]
but in sorted order
• Initialization: j = 2 A[1] is sorted

• Maintenance: Move A[j-1], A[j-2],... one position to the right until the position
for A[j] is found
• Termination: j = n+1 A[1, …, n] is sorted The entire array is sorted.

1 5 2 4 6 1 3 4 2 4 5 6 1 3

A 1, …, i i+1, …, j-1 j
2 2 5 4 6 1 3 5 1 2 4 5 6 3
A’ 1, …, i i+1 I+2, …, j

3 2 4 5 6 1 3 1 2 3 4 5 6

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 11 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 Exact Analysis of Insertion Sort
InsertionSort(A) cost # of times
1. for j = 2 to A.length c1 n
2. key = A[j] c2 n-1
// insert A[j] into the sorted sequence A[1, …, j-1] 0 n-1
3. i = j-1 c4 n-1 n

4. while i > 0 and A[i] > key c5 ∑

j=2
tj
n
5. A[i+1] = A[i] // slide right c6 ∑
j=2
(tj − 1)
n
6. i = i-1 c7 ∑
j=2
(tj − 1)

7. A[i+1] = key // insert c8 n-1

8. return A

• Line 1 is executed (n-1) + 1 times

• tj: # of times the while loop test for value j (i.e., 1 + # of elements that have to
be slid right to insert the j-th item)
• Step 5 is executed t2 + t3 + ... + tn times
• Step 6 is executed (t2 - 1) + (t3 - 1) + ... + (tn - 1) times
n n n
Run time: T(n) = c1n + c2(n − 1) + c4(n − 1) + c5 ∑ tj + c6 ∑ (tj − 1) + c7 ∑ (tj − 1) + c8(n − 1)
j=2 j=2 j=2

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 12 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 Exact Analysis of Insertion Sort
InsertionSort(A) cost # of times
1. for j = 2 to A.length c1 n
2. key = A[j] c2 n-1
// insert A[j] into the sorted sequence A[1, …, j-1] 0 n-1
3. i = j-1 c4 n-1 n

4. while i > 0 and A[i] > key c5 ∑

j=2
tj
n
5. A[i+1] = A[i] // slide right c6 ∑
j=2
(tj − 1)
n
6. i = i-1 c7 ∑
j=2
(tj − 1)

7. A[i+1] = key // insert c8 n-1

8. return A
n n n
• Run time: T(n) = c1n + c2(n − 1) + c4(n − 1) + c5 ∑ tj + c6 ∑ (tj − 1) + c7 ∑ (tj − 1) + c8(n − 1)
j=2 j=2 j=2

• Best case: if the input is already sorted, all tj’s are 1

• Linear: T(n) = (c1 + c2 + c4 + c5 + c8)n − (c2 + c4 + c5 + c8)
• Worst case: if the input is in reverse sorted order, tj = j, ∀ j
c5 + c6 + c7 2 c5 c6 c7
• Quadratic: T(n) = ( )n + (c1 + c2 + c4 + − − + c8)n − (c2 + c4 + c5 + c8)
2 2 2 2

Conclusion: Doing exact analysis is often hard (and tedious). Can we do better?
Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 13 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 Quick Summary
Problem
• Input: a sequence of n numbers <a1, a2, ..., an>.
• Output: a permutation <a1', a2', ..., an'> such that a1' ≤ a2’ ≤ … ≤ an'.

Input: [8, 6, 9, 7, 5, 2, 3]
Instance
Output: [2, 3, 5, 6, 7, 8, 9]

Algorithm: Insertion sort

• Work well for small inputs
• Incremental: having sorted A[1..j-1], insert A[j] yielding sorted A[1..j]
• Memory: in-place
• Rearrange array A, with a constant # of variables (we only use key to store A[j])
• Running time
• Best case: input sorted already, #iterations of while loop is 1 → linear
• Worst case: input sorted in reverse, #iterations of while loop is j → quadratic
• Average case: all permutations equally likely, #iterations of while loop is about j/2 → quadratic

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 14 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 Asymptotic Analysis

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 15 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 Complexity
During exact analysis, each line corresponds to several steps, each step
requires a constant running time

Computational complexity: an abstract measure of time and space

necessary to execute an algorithm as functions of its “input size”
• Time complexity running time (in terms of steps)

• Space complexity memory requirement

Input size: the number of alphabet symbols needed to encode the input
• sort n integers input size: n

Step: primitive operation

• The time to execute a primitive operation must be constant: it must not
increase as the input size grows
Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 16 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 Asymptotic Analysis
Asymptotic analysis looks at growth of T(n) as n → ∞ T(n) Asymptotic
upper bound
Θ notation: Drop low-order terms and ignore the leading constant
• e.g., 8n3 - 4n2 + 5n - 2 = Θ(n3) Asymptotic
lower bound
• As n grows large, lower-order Θ algorithms outperform (i.e.,
run faster than) higher-order algorithms n

Insertion sort
• Worst case: input sorted in reverse, while loop is Θ(j)
n n
j) = Θ(n 2)
∑ ∑
T(n) = Θ( j) = Θ( Quadratic
j=2 j=2
• Average case: all permutations equally likely, while loop is executed about j/2 times
each iteration
n n
j j
) = Θ(n 2) Quadratic
∑ 2 ∑2
T(n) = Θ( ) = Θ(
j=2 j=2
• Best case: if the input is already sorted, all tj’s are 1.
n n

∑ ∑
T(n) = Θ(1) = Θ( 1) = Θ(n) Linear
j=2 j=2

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 17 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 Upper Bounding Function

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 18 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 O: Upper Bounding Function
De nition
• f(n) = O(g(n)) if ∃ c > 0 and n0 > 0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n0
Intuition
• f(n) “≤” g(n) when we ignore constant multiples and small values of n
Veri cation
• How to verify O (Big-Oh) relationships?
f(n)
• f(n) = O(g(n)) when lim ∈ [0, ∞) if the limit exists
n→∞ g(n)

c·g(n)

f(n): nonnegative function f(n)

n: natural number

n
n0
Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 19 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
fi
 O: Upper Bounding Function
De nition
• f(n) = O(g(n)) if ∃ c > 0 and n0 > 0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n0

Practice
c·g(n)
• 3n2 + n = O(n2)
f(n)
• 3n2 + n = O(n)
• 3n2 + n = O(n3)

n
n0

f(n)
f(n) = O(g(n)) when lim ∈ [0, ∞) if the limit exists
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 20 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 O: Upper Bounding Function
De nition
• f(n) = O(g(n)) if ∃ c > 0 and n0 > 0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n0

Practice
c·g(n)
• 3n2 + n = O(n2)
f(n)
• 3n2 + n = O(n)
• 3n2 + n = O(n3)

n
3n2 +n≤ c·n2? n0

f(n)
f(n) = O(g(n)) when lim ∈ [0, ∞) if the limit exists
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 21 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 O: Upper Bounding Function
De nition
• f(n) = O(g(n)) if ∃ c > 0 and n0 > 0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n0

Practice
c·g(n)
• 3n2 + n = O(n2)
f(n)
• 3n2 + n = O(n)
• 3n2 + n = O(n3)

n
3n2 +n≤ c·n2? n0

Take c = 4, n0 = 1

f(n)
f(n) = O(g(n)) when lim ∈ [0, ∞) if the limit exists
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 22 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 O: Upper Bounding Function
De nition
• f(n) = O(g(n)) if ∃ c > 0 and n0 > 0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n0

Practice
c·g(n)
• 3n2 + n = O(n2) Yes
f(n)
• 3n2 + n = O(n)
• 3n2 + n = O(n3)

n
3n2 +n≤ c·n2? n0

Take c = 4, n0 = 1

f(n)
f(n) = O(g(n)) when lim ∈ [0, ∞) if the limit exists
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 23 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 O: Upper Bounding Function
De nition
• f(n) = O(g(n)) if ∃ c > 0 and n0 > 0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n0

Practice
c·g(n)
• 3n2 + n = O(n2) Yes
f(n)
• 3n2 + n = O(n) No
• 3n2 + n = O(n3)

n
3n2 +n≤ c·n2? n0

Take c = 4, n0 = 1

f(n)
f(n) = O(g(n)) when lim ∈ [0, ∞) if the limit exists
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 24 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 O: Upper Bounding Function
De nition
• f(n) = O(g(n)) if ∃ c > 0 and n0 > 0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n0

Practice
c·g(n)
• 3n2 + n = O(n2) Yes
f(n)
• 3n2 + n = O(n) No
• 3n2 + n = O(n3) Yes

n
3n2 +n≤ c·n2? n0

Take c = 4, n0 = 1

f(n)
f(n) = O(g(n)) when lim ∈ [0, ∞) if the limit exists
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 25 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 Lower Bounding Function

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 26 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 Ω: Lower Bounding Function
De nition
• f(n) = Ω(g(n)) if ∃ c > 0 and n0 > 0 such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n0
Intuition
• f(n) “≥” g(n) when we ignore constant multiples and small values of n
Veri cation
• How to verify Ω (Big-Omega) relationships?
f(n)
• f(n) = Ω(g(n)) when lim ∈ (0,∞] if the limit exists
n→∞ g(n)

f(n)

f(n): nonnegative function c·g(n)

n: natural number

n
n0
Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 27 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
fi
 Ω: Lower Bounding Function
De nition
• f(n) = Ω(g(n)) if ∃ c > 0 and n0 > 0 such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n0

Practice
f(n)
• 3n2 + n = Ω(n2)
c·g(n)
• 3n2 + n = Ω(n)
• 3n2 + n = Ω(n3)

n
n0

f(n)
f(n) = Ω(g(n)) when lim ∈ (0,∞] if the limit exists
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 28 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 Ω: Lower Bounding Function
De nition
• f(n) = Ω(g(n)) if ∃ c > 0 and n0 > 0 such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n0

Practice
f(n)
• 3n2 + n = Ω(n2) Yes
c·g(n)
• 3n2 + n = Ω(n)
• 3n2 + n = Ω(n3)

n
n0

f(n)
f(n) = Ω(g(n)) when lim ∈ (0,∞] if the limit exists
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 29 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 Ω: Lower Bounding Function
De nition
• f(n) = Ω(g(n)) if ∃ c > 0 and n0 > 0 such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n0

Practice
f(n)
• 3n2 + n = Ω(n2) Yes
c·g(n)
• 3n2 + n = Ω(n) Yes
• 3n2 + n = Ω(n3)

n
n0

f(n)
f(n) = Ω(g(n)) when lim ∈ (0,∞] if the limit exists
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 30 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 Ω: Lower Bounding Function
De nition
• f(n) = Ω(g(n)) if ∃ c > 0 and n0 > 0 such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n0

Practice
f(n)
• 3n2 + n = Ω(n2) Yes
c·g(n)
• 3n2 + n = Ω(n) Yes
• 3n2 + n = Ω(n3) No

n
n0

f(n)
f(n) = Ω(g(n)) when lim ∈ (0,∞] if the limit exists
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 31 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 Tightly Bounding Function

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 32 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 Θ: Tightly Bounding Function
De nition
• f(n) = Θ(g(n)) if ∃ c1, c2 > 0 and n0 > 0 such that 0 ≤ c1·g(n) ≤ f(n) ≤ c2·g(n)
for all n ≥ n0
Intuition
• f(n) “=” g(n) when we ignore constant multiples and small values of n
Veri cation
• How to verify Θ (Big-Theta) relationships?
• Show both “big Oh” (O) and “Big Omega” (Ω) relationships
f(n)
• f(n) = Θ(g(n)) when lim ∈ (0,∞) if the limit exists
n→∞ g(n) c1·g(n)
f(n)

c2·g(n)

n
Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 33 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
fi
 Θ: Tightly Bounding Function
De nition
• f(n) = Θ(g(n)) if ∃ c1, c2 > 0 and n0 > 0 such that 0 ≤ c1·g(n) ≤ f(n) ≤ c2·g(n)
for all n ≥ n0

Practice c1·g(n)
f(n)
• 3n2 + n = Θ(n2)
c2·g(n)
• 3n2 + n = Θ(n)
• 3n2 + n = Θ(n3) n

f(n)
f(n) = Θ(g(n)) when lim ∈ (0,∞) if the limit exists
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 34 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 Θ: Tightly Bounding Function
De nition
• f(n) = Θ(g(n)) if ∃ c1, c2 > 0 and n0 > 0 such that 0 ≤ c1·g(n) ≤ f(n) ≤ c2·g(n)
for all n ≥ n0

Practice c1·g(n)
Yes f(n)
• 3n2 + n = Θ(n2)
c2·g(n)
• 3n2 + n = Θ(n)
• 3n2 + n = Θ(n3) n

f(n)
f(n) = Θ(g(n)) when lim ∈ (0,∞) if the limit exists
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 35 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 Θ: Tightly Bounding Function
De nition
• f(n) = Θ(g(n)) if ∃ c1, c2 > 0 and n0 > 0 such that 0 ≤ c1·g(n) ≤ f(n) ≤ c2·g(n)
for all n ≥ n0

Practice c1·g(n)
Yes f(n)
• 3n2 + n = Θ(n2)
No c2·g(n)
• 3n2 + n = Θ(n)
• 3n2 + n = Θ(n3) n

f(n)
f(n) = Θ(g(n)) when lim ∈ (0,∞) if the limit exists
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 36 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 Θ: Tightly Bounding Function
De nition
• f(n) = Θ(g(n)) if ∃ c1, c2 > 0 and n0 > 0 such that 0 ≤ c1·g(n) ≤ f(n) ≤ c2·g(n)
for all n ≥ n0

Practice c1·g(n)
Yes f(n)
• 3n2 + n = Θ(n2)
No c2·g(n)
• 3n2 + n = Θ(n)
• 3n2 + n = Θ(n3) No
n

f(n)
f(n) = Θ(g(n)) when lim ∈ (0,∞) if the limit exists
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 37 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 Untightly Upper Bounding Functions
&
Untightly Lower Bounding Functions

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 38 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 o: Untightly Upper Bounding Function
De nition
• f(n) = o(g(n)) if ∀ c > 0, ∃ n0 > 0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n0
Intuition
• f(n) “<” any constant multiple of g(n) when we ignore small values of n
Veri cation
• How to verify o (Little-Oh) relationships?
f(n)
• f(n) = o(g(n)) when lim =0
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 39 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
fi
 o: Untightly Upper Bounding Function
De nition
• f(n) = o(g(n)) if ∀ c > 0, ∃ n0 > 0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n0

Practice
• 3n2 + n = o(n2)
• 3n2 + n = o(n)
• 3n2 + n = o(n3)

f(n)
f(n) = o(g(n)) when lim =0
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 40 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 o: Untightly Upper Bounding Function
De nition
• f(n) = o(g(n)) if ∀ c > 0, ∃ n0 > 0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n0

Practice
• 3n2 + n = o(n2) No
• 3n2 + n = o(n)
• 3n2 + n = o(n3)

f(n)
f(n) = o(g(n)) when lim =0
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 41 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 o: Untightly Upper Bounding Function
De nition
• f(n) = o(g(n)) if ∀ c > 0, ∃ n0 > 0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n0

Practice
• 3n2 + n = o(n2) No
• 3n2 + n = o(n) No
• 3n2 + n = o(n3)

f(n)
f(n) = o(g(n)) when lim =0
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 42 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 o: Untightly Upper Bounding Function
De nition
• f(n) = o(g(n)) if ∀ c > 0, ∃ n0 > 0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n0

Practice
• 3n2 + n = o(n2) No
• 3n2 + n = o(n) No
• 3n2 + n = o(n3) Yes

f(n)
f(n) = o(g(n)) when lim =0
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 43 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 ω: Untightly Lower Bounding Function
De nition
• f(n) = ω(g(n)) if ∀ c > 0, ∃ n0 > 0 such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n0
Intuition
• f(n) “>” any constant multiple of g(n) when we ignore small values of n
Veri cation
• How to verify ω (Little-Omega) relationships?
f(n)
• f(n) = ω(g(n)) when lim =∞
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 44 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
fi
 ω: Untightly Lower Bounding Function
De nition
• f(n) = ω(g(n)) if ∀ c > 0, ∃ n0 > 0 such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n0

Practice
• 3n2 + n = ω(n2)
• 3n2 + n = ω(n)
• 3n2 + n = ω(n3)

f(n)
f(n) = o(g(n)) when lim =∞
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 45 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 ω: Untightly Lower Bounding Function
De nition
• f(n) = ω(g(n)) if ∀ c > 0, ∃ n0 > 0 such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n0

Practice
• 3n2 + n = ω(n2) No
• 3n2 + n = ω(n)
• 3n2 + n = ω(n3)

f(n)
f(n) = o(g(n)) when lim =∞
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 46 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 ω: Untightly Lower Bounding Function
De nition
• f(n) = ω(g(n)) if ∀ c > 0, ∃ n0 > 0 such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n0

Practice
• 3n2 + n = ω(n2) No
• 3n2 + n = ω(n) Yes
• 3n2 + n = ω(n3)

f(n)
f(n) = o(g(n)) when lim =∞
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 47 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 ω: Untightly Lower Bounding Function
De nition
• f(n) = ω(g(n)) if ∀ c > 0, ∃ n0 > 0 such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n0

Practice
• 3n2 + n = ω(n2) No
• 3n2 + n = ω(n) Yes
• 3n2 + n = ω(n3) No

f(n)
f(n) = o(g(n)) when lim =∞
n→∞ g(n)

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 48 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fi
 Comparison: o, O, Θ, Ω, ω

Tips Π= o O Θ Ω ω
• o: >>
• O: > f(n) = 3n2 + n = Π(n) No No No Yes Yes

• Θ: =
f(n) = 3n2 + n = Π(n2) No Yes Yes Yes No
• Ω: <
• ω: << f(n) = 3n2 + n = Π(n3) Yes Yes No No No

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 49 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 Meaning of Asymptotic Notation

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 50 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 Meaning of Asymptotic Notation
“An algorithm has the worst-case running time O(f(n))”
• There is a constant c such that for every n big enough, every execution on
an input of size n takes at most c·f(n) time.

“An algorithm has the worst-case running time Ω(f(n))”

• There is a constant c such that for every n big enough, at least one
execution on an input of size n takes at least c·f(n) time.

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 51 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 Properties for Asymptotic Analysis
Transitivity
• If f(n) = Π(g(n)) and g(n) = Π(h(n)), then f(n) = Π(h(n)), where Π = O, o, Ω, ω,
or Θ
Rule of sums
• f(n) + g(n) = Π(max{f(n), g(n)}), where Π = O, Ω, or Θ
Rule of products
• If f1(n) = Π(g1(n)) and f2(n) = Π(g2(n)), then f1(n)·f2(n) = Π(g1(n)·g2(n)), where Π
= O, o, Ω, ω, or Θ
Transpose symmetry: f(n) = O(g(n)) iff g(n) = Ω(f(n)).
Transpose symmetry: f(n) = o(g(n)) iff g(n) = ω(f(n)).
Re exivity: f(n) = Π(f(n)), where Π = O, Ω, or Θ.
Symmetry: f(n) = Θ(g(n)) iff g(n) = Θ(f(n))

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 52 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
fl
 Asymptotic Analysis vs. Runtime
Runtime comparison: assume 1 BIPS,1 instruction/op.

Time Big-Oh n=10 n=100 n=104 n=106 n=108

500 O(1) 5x10-7 sec 5x10-7 sec 5x10-7 sec 5x10-7 sec 5x10-7 sec

3n O(n) 3x10-8 sec 3x10-7 sec 3x10-5 sec 0.003 sec 0.3 sec

n lg n O(n lg n) 3x10-8 sec 6x10-7 sec 1x10-4 sec 0.018 sec 2.5 sec

n2 O(n2) 1x10-7 sec 1x10-5 sec 0.1 sec 16.7 min 116 days

n3 O(n3) 1x10-6 sec 0.001 sec 16.7 min 31.7 years ∞

2n O(2n) 1x10-6 sec 4x1011 cent. ∞ ∞ ∞

n! O(n!) 0.003 sec ∞ ∞ ∞ ∞

Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 53 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
 “Efficient” Algorithms
In theoretical computer science, usually every polynomial time algorithm is considered
‘e cient'.

Polynomial-time complexity: O(p(n)), where n is the input size and p(n) is a polynomial
function of n (p(n) = nO(1)).
1 constant
lg*n Iterated logarithm
lg (O(1))n = lg lg ... lg n -
lg n logarithmic
lg O(1)n = (lg n)O(1) polylogarithmic
n sublinear “e cient”
n linear
n lg n loglinear
n2 quadratic
n3 cubic
n4 quartic
2n, 3n, . . . exponential
n! factorial
nn
Lecture 2 112-2 (Spring 2024) Algorithms (EE4033-01) - 54 - Shao-Hua Sun (孫紹華) Assistant Prof. in EE @ NTU
ffi
ffi