Algorithm Design and Analysis
Lecture 02
Algorithm Analysis I
Mohammed Alqmase
Frequency Count Method
Frequency Count Method
Definition: Count the number of times basic operations
are executed.
Name Operations Time
Arithmetic Operations +, -, *, / one unit of time
Assignment Operators ≔, ← one unit of time
Comparisons Operations =, ≠, <, ≤, >, ≥ one unit of time
Control Statements return, break, continue one unit of time
Frequency Count Method
Function sum(a, b):
sum = a + b
return sum
EndFunction
Time Function f(n): 3 units of time
Frequency Count Method
Function sumArray(arr, n):
sum = 0
For i = 0 to n-1:
sum = sum + arr[i]
EndFor
return sum
EndFunction
Time Function f(n): 2n + 3
Frequency Count Method
Function findMax(arr, n):
max = arr[0]
For i = 1 to n-1:
If arr[i] > max:
max = arr[i]
EndFor
return max
EndFunction
Time Function f(n): 2n + 3 In the worst case
Time Function f(n): n+4 In the best case
Frequency Count Method i=i+1
For( i=0; i<n; i++ )
stmt
Time Function f(n): 𝟏 + 𝒏 + 𝟏 + 𝟐𝒏 + 𝒏 = 𝟒𝒏 + 𝟐
For( i=0; i < 10 ; i++ )
stmt
Time Function f(n): 32 Always 32, regardless of input size n.
Frequency Count Method i=i+1
For( i=0; i<n; i++ ) Time Function f(n): 4n + 2
stmt
i=0
while(i < n) {
stmt
i++ Time Function f(n): 4n + 2
}
Frequency Count Method i=i+1
For( i=0; i<n; i++ ) Time Function f(n): 4n + 2
stmt
For( i=n; i>=0; i-- )
stmt Time Function f(n): 4n + 2
Frequency Count Method i=i+2
For( i=0; i<n; i+=2 )
stmt
𝟏 𝟐𝒏 𝟏
Time Function f(n): 𝟏+ 𝒏 + 𝟏 + + 𝒏 = 𝟐𝒏 + 𝟐
𝟐 𝟐 𝟐
Frequency Count Method i=i*2
Iteration i stmt execution i*=2
For( i=1; i<n; i*=2 )
1 𝟏 = 𝟐𝟎 1 i*2=2
stmt
𝟐𝒌 ≥ 𝒏 2 𝟐 = 𝟐𝟏 1 i*2=4
3 𝟒 = 𝟐𝟐 1 i*2=8
log 𝟐 𝟐𝒌 ≥ log 𝟐 𝒏
4 𝟖 = 𝟐𝟑 1 i * 2 = 16
𝒌log 𝟐 𝟐 ≥ log 𝟐 𝒏 .
.
.
𝒌 ≥ log 𝟐 𝒏 k+1 𝟐𝒌
For( 𝒌 = 𝟎; 𝒌 < 𝒍𝒐𝒈𝒏; 𝒌++)
stmt
Time Function f(n): 𝟏 + 𝒍𝒐𝒈𝟐 𝒏 + 𝟏 + 𝟐𝒍𝒐𝒈𝟐 𝒏 + 𝒍𝒐𝒈𝟐 𝒏 = 𝟒𝒍𝒐𝒈𝟐 𝒏 + 𝟐
Frequency Count Method i=i*2
Iteration i stmt execution i*=2
For( i=1; i<n; i*=2 )
1 𝟏 = 𝟐𝟎 1 i*2=2
stmt
𝟐𝒌 ≥ 𝒏 2 𝟐 = 𝟐𝟏 1 i*2=4
3 𝟒 = 𝟐𝟐 1 i*2=8
log 𝟐 𝟐𝒌 ≥ log 𝟐 𝒏
4 𝟖 = 𝟐𝟑 1 i * 2 = 16
𝒌log 𝟐 𝟐 ≥ log 𝟐 𝒏 .
.
.
𝒌 ≥ log 𝟐 𝒏 k+1 𝟐𝒌
For( 𝒌 = 𝟎; 𝒌 < 𝒍𝒐𝒈𝒏; 𝒌++)
stmt
Time Function f(n): 𝟏 + 𝒍𝒐𝒈𝟐 𝒏 + 𝟏 + 𝟐𝒍𝒐𝒈𝟐 𝒏 + 𝒍𝒐𝒈𝟐 𝒏 = 𝟒𝒍𝒐𝒈𝟐 𝒏 + 𝟐
Frequency Count Method
For( i=1; i<n; i*=3 )
stmt
Time Function f(n): 𝟏 + 𝒍𝒐𝒈𝟑 𝒏 + 𝟏 + 𝟐𝒍𝒐𝒈𝟑 𝒏 + 𝒍𝒐𝒈𝟑 𝒏 = 𝟒𝒍𝒐𝒈𝟑 𝒏 + 𝟐
Frequency Count Method
For( i=1; 𝑖 ∗ 𝒊 < 𝒏; i++ ) For( i=0; 𝒊 < 𝒏; i++)
stmt stmt
𝑖∗𝒊<𝒏
𝒊𝟐 < 𝒏
𝒊< 𝒏
Time Function f(n): 𝟏+ 𝒏 + 𝟏 + 𝟐 𝒏 + 𝒏 = 𝟒 𝒏+𝟐
Frequency Count Method
function1 ( n ):
For( i=0; i<n; i++ ){
stmt stmt executed: 𝟐𝒏
}
For( a=0; a<n; a++ ) {
stmt
}
function2 ( n ):
For( i=0; i<n; i++ ){
For( a=0; a<n; a++ ) stmt executed: 𝒏𝟐
stmt
}
Frequency Count Method 𝒊 𝒋 No. of 𝒔𝒕𝒎𝒕 Execute
0 0 0
function( n ): 1
0
1
1
For( 𝒊 = 𝟎; 𝒊 < 𝒏; 𝒊 + + ){ 0
2 1 2
2
For( 𝒋 = 𝟎; 𝒋 < 𝒊 ; 𝒋 + + ){ 0
1
3 3
𝒔𝒕𝒎𝒕 2
3
} .
.
.
} 0
..
n n
.
n
stmt exectue:
𝒏 𝒏 𝒏+𝟏
𝟎 + 𝟏 + 𝟐 + 𝟑 + ⋯+ 𝐧 = 𝐢 = = 𝒎
𝒊=𝟎 𝟐
Frequency Count Method
function( n ):
For( 𝒊 = 𝟎; 𝒊 < 𝒏; 𝒊 + + ){ 𝒏 𝒏+𝟏
= = 𝒎
𝟐
For( 𝒋 = 𝟎; 𝒋 < 𝒊 ; 𝒋 + + ){
𝒔𝒕𝒎𝒕
}
}
Frequency Count Method
function( n ):
1 n+1 2n
For( 𝒊 = 𝟎; 𝒊 < 𝒏; 𝒊 + + ){ 𝒏 𝒏+𝟏
= 𝒎
n m+1 2m 𝟐
For( 𝒋 = 𝟎; 𝒋 < 𝒊 ; 𝒋 + + ){
𝒔𝒕𝒎𝒕 m
Time Function 𝒇(𝒏): 𝟒𝒏 + 𝟒𝒎 + 𝟐
}
𝒏 𝒏+𝟏
= 𝟒𝒏 + 𝟒 + 𝟐
} 𝟐
= 𝟒𝒏 + 𝟐𝒏(𝒏 + 𝟏) + 𝟐
= 𝟒𝒏 + 𝟐𝒏𝟐 + 𝟐𝒏 + 𝟐
= 𝟐𝒏𝟐 + 𝟔𝒏 + 𝟐
Frequency Count Method
𝒇(𝒏) = 𝟐𝒏𝟐 + 𝟔𝒏 + 𝟐
𝟐
𝒇(𝒏) = 𝑶( 𝒏 )
Asymptotic Notation
Asymptotic Notation
Asymptotic Notation
❖ A method of describing the behavior of algorithms as
the input size (𝑛) becomes very large.
❖ 𝐼𝑛𝑝𝑢𝑡 𝑠𝑖𝑧𝑒 (𝑛): The number of elements or data items
an algorithm processes.
Asymptotic Notation
❖ Focuses on the 𝒈𝒓𝒐𝒘𝒕𝒉 𝒓𝒂𝒕𝒆 of an algorithm rather
than its exact runtime.
Asymptotic Notation
❖ Focuses on the 𝒈𝒓𝒐𝒘𝒕𝒉 𝒓𝒂𝒕𝒆 of an algorithm rather
than its exact runtime.
❖ 𝐺𝑟𝑜𝑤𝑡ℎ 𝑟𝑎𝑡𝑒: Describes how the runtime of an algorithm
increases with input size.
Asymptotic Notation
❖ Key idea: Abstract away low-level details and concentrate
on long-term trends.
𝒇(𝒏) = 𝟐𝒏𝟐 + 𝟔𝒏 + 𝟐
𝟐
𝒇(𝒏) = 𝑶( 𝒏 )
Why Asymptotic Analysis?
❖ Enables comparison of algorithms independent of
hardware or implementation.
❖ Simplifies understanding of computational complexity.
What is Order of Growth?
❖ 𝑂𝑟𝑑𝑒𝑟 𝑜𝑓 𝐺𝑟𝑜𝑤𝑡ℎ: Classifies algorithms based on their
dominant growth rate.
Order Big-Theta
Constant Θ(1)
Logarithmic Θ(log 𝑛)
Linear Θ(𝑛)
Quadratic Θ(𝑛2 )
Exponential Θ(2𝑛 )
What is Order of Growth?
❖ 𝑂𝑟𝑑𝑒𝑟 𝑜𝑓 𝐺𝑟𝑜𝑤𝑡ℎ: Classifies algorithms based on their
dominant growth rate.
Why Focus on Order of Growth?
❖ Simplifies performance analysis by focusing on the
𝑑𝑜𝑚𝑖𝑛𝑎𝑛𝑡 𝑡𝑒𝑟𝑚 of 𝒇(𝒏)
❖ Low-order terms and constants are ignored as 𝒏 → ∞
𝒇(𝒏) = 𝟐𝒏𝟐 + 𝟔𝒏 + 𝟐
𝒇(𝒏) = 𝑶( 𝒏𝟐 )
Why Focus on Order of Growth?
❖ Simplifies performance analysis by focusing on the
𝑑𝑜𝑚𝑖𝑛𝑎𝑛𝑡 𝑡𝑒𝑟𝑚 of 𝒇(𝒏)
❖ Low-order terms and constants are ignored as 𝒏 → ∞
𝒇(𝒏) = 𝟐𝒏𝟐 + 𝟔𝒏 + 𝟐
𝒇(𝒏) = 𝑶( 𝒏𝟐 )
Why Focus on Order of Growth?
❖ 𝑫𝒐𝒎𝒊𝒏𝒂𝒏𝒕 𝒕𝒆𝒓𝒎: The term with the highest growth rate
in 𝑓(𝑛)
❖ Example
𝒇(𝒏) = 𝟐𝒏𝟐 + 𝟔𝒏 + 𝟐
o Dominant term: 𝟐𝒏𝟐
o Lower-order terms: 𝟔𝒏 + 𝟐
o 𝑓(𝑛) ∼ 𝟐𝒏𝟐 as 𝑛 → ∞
Asymptotic Analysis
Asymptotic Analysis: Evaluates an algorithm’s growth rate as the
input size (𝑛) approaches infinity.
❖ Focuses on dominant terms and ignores constants.
❖ Uses notations:
➢ Big-O (𝑶)
➢ Big-Omega (𝛀)
➢ Big-Theta (Θ)
Asymptotic Notations
Notation Notations Definition Use Case
Big-O 𝑂(𝑓(𝑛)) Upper Bound Worst-case
Big-Omega Ω(𝑓(𝑛)) Lower Bound Best-case
Big-Theta Θ(𝑓(𝑛)) Tight Bound Average-case
Choosing the Right Notation
❖ Big-O (𝑶): Focus on scalability and performance in the worst-case.
❖ Big-Omega (𝛀): Ideal for analyzing guaranteed minimum performance.
❖ Big-Theta (𝚯): Best when both bounds are equally important.
Case Analysis
Case Analysis: Evaluates an algorithm’s performance in different scenarios:
❖ Best Case: Minimum time needed when input is optimal.
❖ Worst Case: Maximum time required for the least favorable input.
❖ Average Case: Expected time for a random input
Case Analysis
𝑙𝑖𝑛𝑒𝑎𝑟𝑆𝑒𝑎𝑟𝑐ℎ( 𝑎𝑟𝑟 , 𝑥 ):
1. 𝑓𝑜𝑟 𝑖 𝑓𝑟𝑜𝑚 0 𝑡𝑜 𝑛:
2. 𝑖𝑓 𝑎𝑟𝑟[𝑖] == 𝑥:
3. 𝑟𝑒𝑡𝑢𝑟𝑛 𝑖
4. 𝑟𝑒𝑡𝑢𝑟𝑛 − 1
❖ Best Case: 𝑂(1)
❖ Worst Case: 𝑂(𝑛)
❖ Average Case: 𝑂(𝑛/2) = 𝑂(𝑛) .
Asymptotic Analysis
𝑙𝑖𝑛𝑒𝑎𝑟𝑆𝑒𝑎𝑟𝑐ℎ( 𝑎𝑟𝑟 , 𝑥 ):
1. 𝑓𝑜𝑟 𝑖 𝑓𝑟𝑜𝑚 0 𝑡𝑜 𝑛:
2. 𝑖𝑓 𝑎𝑟𝑟[𝑖] == 𝑥:
3. 𝑟𝑒𝑡𝑢𝑟𝑛 𝑖
4. 𝑟𝑒𝑡𝑢𝑟𝑛 − 1
❖ 𝛺(1)
❖ 𝑂(𝑛)
❖ Θ(𝑛) .
