Algorithm Analysis

and Design
Lecture 3

1
 Recursion
Growth-Rate Functions – Recursive Algorithms
 Tower of Hanoi
void hanoi(int n, char source, char dest, char spare) { //Cost
if (n > 0) { //c1
hanoi(n-1, source, spare, dest); //c2
cout << "Move top disk from pole " << source //c3
<< " to pole " << dest << endl;
hanoi(n-1, spare, dest, source); //c4
}
}

• The time-complexity function T(n) of a recursive algorithm is

defined in terms of itself, and this is known as recurrence equation
for T(n).
• To find the growth-rate function for a recursive algorithm, we have
to solve its recurrence relation. 3
 Growth-Rate Functions – Hanoi Towers
• What is the cost of hanoi(n,’A’,’B’,’C’)?

when n=0
T(0) = c1

when n>0
T(n) = c1 + T(n-1) + c2 + T(n-1)
= 2*T(n-1) + (c1+c2)
T(n) = 2*T(n-1) + c
Recurrence equation for the growth-rate function of hanoi-towers algorithm

• Now, we have to solve this recurrence equation to find the growth-rate function
of hanoi-towers algorithm

4
 Growth-Rate Functions – Hanoi Towers (cont.)
• There are many methods to solve recurrence equations, but we will use a simple
method known as repeated substitutions.

T(n) = 2*T(n-1) + c
= 2 * (2*T(n-2)+c) + c
= 2 * (2* (2*T(n-3)+c) + c) + c
= 23 * T(n-3) + (22+21+20)*c (assuming n>2)
when substitution repeated i-1th times
= 2i * T(n-i) + (2i-1+ ... +21+20)*c
when i=n
= 2n * T(0) + n−(21n-1+ ... +21+20)*c
= 2n * c1 + ( ∑ 2)*c i
2a = 2 + 4 + 8 + .. + 2n-1 + 2n
i= 0 a = 1 + 2 + 4 + 8 + .. + 2n-1
2a – a is your result 2n - 1

= 2n * c1 + ( 2n-1 )*c = 2n*(c1+c) – c ➔ So, the growth rate function is O(2n)

5
 More Recursive Algorithms
int fact(int n) {
if (n ==0)
return (1);
else
return (n * fact(n-1));
}

T(n) = T(n-1) + c
= (T(n-2) + c) + c
= (T(n-3) + c) + c + c
= (T(n-i) + i*c)
when i=n → T(0) + n*c ➔ T(n) = O(n)
 Tracing the call fact (3)

N=0
if (N==0) true
return (1)
N=1 N=1
if (N==0) false if (N==0) false
return (1*fact(0)) return (1*fact(0))
N=2 N=2 N=2
if (N==0) false if (N==0) false if (N==0) false
return (2*fact(1)) return (2*fact(1)) return (2*fact(1))
N=3 N=3 N=3 N=3
if (N==0) false if (N==0) false if (N==0) false if (N==0) false
return (3*fact(2)) return (3*fact(2)) return (3*fact(2)) return (3*fact(2))
After original After 1st call After 2nd call After 3rd call
call 7

11/8/2023
 Tracing the call fact (3)

N=1
if (N==0) false
return (1* 1)
N=2 N=2
if (N==0) false if (N==0) false
return (2*fact(1)) return (2* 1)
N=3 N=3 N=3
if (N==0) false if (N==0) false if (N==0) false
return (3*fact(2)) return (3*fact(2)) return (3* 2)
After return After return After return return 6
from 3rd call from 2nd call from 1st call 8

11/8/2023
 More Recursive Algorithms
bool isPalindrome (string s) {
if (s.length() <= 1)
return true;
return (s[0]==s[s.length()-1])&&
isPalindrome(s.substr(1,s.length()-2));
}

T(n) = T(n-2) + c
= (T(n-4) + c) + c
= (T(n-6) + c) + c + c
= (T(n-i) + i/2*c)
when i=n → T(0) + n/2*c ➔ T(n) = O(n)
 More Recursive Algorithms

int fib(int n) { //1 1 2 3 5 8 13 21 34 ..

if (n == 1) return 1; if (n == 2) return 1;
else
return fib(n-1) + fib(n-2);
}
T(n) = ?
 More Recursive Algorithms

Count positive integers in an array recursively?

int countPos(int* A, int j) {

}
 More Recursive Algorithms

Count positive integers in an array recursively?

int countPos(int* A, int j) { //1st call countPos(A, n-1)
if (j < 0) return 0;
if (A[j] > 0) return 1 + countPos(A, j-1);
else return 0 + countPos(A, j-1);
}
T(n) = T(n-1) + c ➔ T(n) = O(n).
Iterative version is also O(n).
 What to Analyze
• An algorithm can require different times to solve different
problems of the same size.
– Eg. Searching an item in a list of n elements using sequential search. ➔ Cost:
1,2,...,n
• Worst-Case Analysis –The maximum amount of time that an
algorithm require to solve a problem of size n.
– This gives an upper bound for the time complexity of an algorithm.
– Normally, we try to find worst-case behavior of an algorithm.
• Best-Case Analysis –The minimum amount of time that an
algorithm require to solve a problem of size n.
– The best case behavior of an algorithm is NOT so useful.
• Average-Case Analysis –The average amount of time that an
algorithm require to solve a problem of size n.
– Sometimes, it is difficult to find the average-case behavior of an algorithm.

Worst-case analysis is more common than average-case analysis.

19
 Sequential Search
int sequentialSearch(const int a[], int item, int n){
for (int i = 0; i < n && a[i]!= item; i++);
if (i == n)
return –1;
return i;
}
Unsuccessful Search: ➔ O(n)

Successful Search:
Best-Case: item is in the first location of the array ➔O(1)
Worst-Case: item is in the last location of the array ➔O(n)
Average-Case: The number of key comparisons 1, 2, ..., n
n
∑i ( n 2 +n)/2
i=1
=
n n ➔ O(n)
20
 Binary Search
We can do binary search if the array is sorted:

int binarySearch(int a[], int size, int x) {

int low =0;
int high = size –1;
int mid; // mid will be the index of
// target when it’s found.
while (low <= high) {
mid = (low + high)/2;
if (a[mid] < x)
low = mid + 1;
else if (a[mid] > x)
high = mid – 1;
else
return mid;
}
return –1;
}
21
 Binary Search – Analysis
• For an unsuccessful search:
– The number of iterations in the loop is log2n + 1
➔ O(log2n)
• For a successful search:
– Best-Case: The number of iterations is 1. ➔ O(1)
– Worst-Case: The number of iterations is log2n +1 ➔ O(log2n)
– Average-Case: The avg. # of iterations < log2n ➔ O(log2n)

0 1 2 3 4 5 6  an array with size 7

3 2 3 1 3 2 3  # of iterations
The average # of iterations = 17/7 = 2.4285 < log27

22
 How much better is O(log2n)?

n O(log2n)
16 4
64 6
256 8
1024 10
16,384 14
131,072 17
262,144 18
524,288 19
1,048,576 20
1,073,741,824 30

23
General Questions
 Test Your Knowledge
• Find the value of K
int k=5;
for(int i=5;i<=12;i++)
k=k+2;
for(int j=2;j<11;j++)
k=k-1;

Addition Rule
K=5+8*2 + 9*(-1)
Loops are independent
25
 Test Your Knowledge
• Find the value of K
int k=4;
for(int i=5;i<=10;i++)
for(int j=12;j>=2;j--)
k=k+2;

Multiplication Rule
K=4+(6*11*2)
Loops are dependent on each other (Nested Loops)

26
 Test Your Knowledge
• Find the value of K

K=5+211(111*2 + 111*(-4))

27
 Test Your Knowledge
• Find the value of K
int k=2;
for(int i=3;i<=7;i++){
for(int j=1;j<5;j++)
k=k+3;
for(int j=1;j<=5;j++)
k=k+1;
}
for(int j=5;j<=11;j++)
k=k+2;
K=2+5(4*3+5*1) + 7*2
28
 Running Time
• Running Time 𝑻(𝑰)
• The running time 𝑇(𝐼) of an algorithm 𝜶 on Input I , is the
time taken by 𝜶 on I until 𝜶 halts.
• Assumption:
• The larger the input size, the larger running time
• Number of inputs of size 𝑛 ∈ 𝑁 is infinite
• Definition
• Best Case Running Time 𝐵 𝑛 (BCRT)
• The BCRT of algorithm 𝛼 on input I is defined as follows
𝐵 𝑛 = 𝐦𝐢𝐧 𝑇 𝐼 𝐼 ℎ𝑎𝑠 𝑠𝑖𝑧𝑒 𝑛} ∪ {0}
• Worst Case Running Time 𝐵 𝑛 (WCRT)
• The WCRT of algorithm 𝛼 on input I is defined as follows
𝐵 𝑛 = 𝐦𝐚𝐱 𝑇 𝐼 𝐼 ℎ𝑎𝑠 𝑠𝑖𝑧𝑒 𝑛} ∪ {0}
Then BCRT≤ 𝑇 𝐼 ≤ WCRT
Note: the Average running time is at worst as the worst case running time 29
 Computing T(I)
Time Number of reputation
P-lines 1 ------------------- 𝑪𝟏 𝒒𝟏
2 ------------------- 𝑪𝟐 𝒒𝟐
3 ------------------- 𝑪𝟑 𝒒𝟑

p ------------------- 𝑪𝒑 𝒒𝒑

• Let pseudo code of an algorithm 𝛼 consists of p lines

• Assume that the execution of line i require time 𝑐𝑖 , 1 ≤ 𝑖 ≤ 𝑝
• Let 𝑞𝑖 the number of times line i is executed on input I
𝑝
• Then the running time 𝑇 𝐼 = σ𝑖=1 𝑐𝑖 𝑞𝑖

30
 Computing T(I): Maximum Algorithm
• Given 𝑎1 , 𝑎2 , … , 𝑎𝑛
• Find 𝑉 = max(𝑎1 , 𝑎2 , … , 𝑎𝑛 )
The algorithm
Time m
1. 𝑉 ← 𝑎1 𝑪𝟏 1
2. for i ← 2 𝑡𝑜 𝑛 𝑪𝟐 (n-2+1)+1=n
3. if ai > V then 𝑉 ← 𝑎𝑖 𝑪𝟑 n-1
4. return 𝑉 𝑪𝟒 1

𝑇 𝐼 = 𝑐1 ∗ 1 + 𝑐2 ∗ 𝑛 + 𝑐3 ∗ 𝑛 − 1 + 𝑐4 ∗ 1
𝑇 𝐼 = 𝑐1 + 𝑐2 𝑛 + 𝑐3 𝑛 − 𝑐3 + 𝑐4
𝑇 𝐼 = (𝑐1 +𝑐4 − 𝑐3 ) + 𝑛(𝑐2 + 𝑐3 )
𝑇 𝐼 = 𝑎 + 𝑏𝑛
𝑇 𝐼 = 𝜃(𝑛)
31
 Computing T(I): Linear Sort
• linear sort
• Given 𝑎1 , 𝑎2 , … , 𝑎𝑛
• Sort the list in ascending order
The algorithm

1. for i← 1 to n − 1 𝑛−1 −1+1+1=𝑛

2. for j ← i + 1 to n 𝑛− 𝑖+1 +1+1=𝑛−𝑖+1
3. If 𝑎𝑖 > 𝑎𝑗 𝑡ℎ𝑒𝑛 𝑛−𝑖
4. temp ← a𝑖 𝑛−𝑖
4. a𝑖 ← a𝑗 𝑛−𝑖
4. a𝑗 ← temp 𝑛−𝑖

32
 Computing T(I): Linear Sort
• linear sort (Cont. )
𝑛−1 𝑛−1

𝑇 𝐼 = 𝑛 + ෍ (𝑛 − 𝑖 + 1) + ෍ 𝑛 − 𝑖
𝑖=1 𝑖=1
𝑛−1 𝑛−1 𝑛−1

𝑇 𝐼 =𝑛+෍ 𝑛+1 +෍𝑛−2෍𝑖

𝑖=1 𝑖=1 𝑖=1
𝑛(𝑛+1) 𝑛2 +𝑛 𝑛2 +𝑛
Note that: σ𝑛𝑖=1 𝑖 = = → σ𝑛−1
𝑖=1 𝑖 = −𝒏
2 2 2
𝑛2 + 𝑛
𝑇 𝐼 =𝑛+ 𝑛−1 𝑛+1 + 𝑛−1 𝑛−2 −𝑛
2
𝑇 𝐼 = 𝑛 + 𝑛2 − 1 + 𝑛2 − 𝑛 − 𝑛2 + 𝑛 + 2𝑛
𝑇 𝐼 = 𝑛2 + 𝑛 − 1
𝑇 𝐼 = 𝜃(𝑛2 )
33
 Computing T(I): Linear Search
• Try linear search
• Given 𝑎1 , 𝑎2 , … , 𝑎𝑛
• Find location of X in (𝑎1 , 𝑎2 , … , 𝑎𝑛 )
The algorithm
1. i← 1
2. while i ≤ 𝑛 and x ≠ ai
3. i← 𝑖 + 1
4. If i≤ n
5. then loc ← 𝑖
6. 𝑒𝑙𝑠𝑒
7. then loc ← 0
8. return loc

34
 Test Your Knowledge
• Find the value of K
int k=5; 1 1

for(int i=1;i<=n;i++) 𝑛−1+1=𝐧 𝒏+𝟏

k=k+2; 𝑛−1+1 n

K=5+(n*2)

35
 Test Your Knowledge
• Find the value of K
int k=5; 1 1

for(int i=1;i<=n;i++) 𝑛−1+1=𝒏 𝒏+𝟏

𝑛
for(int j=1;i<=m;j++) m
෍ 𝑚+1 = 𝒎+𝟏 𝒏
𝑗=1
𝑛 𝑚
k=k+2; 𝑚∗𝑛
෍෍1 = 𝑚 ∗𝑛
𝑖=1 𝑗=1

K=5+(n*m)*2
36
 Computing T(I): Binary Search
• Given a value X and a set of values 𝑎1 , 𝑎2 , … , 𝑎𝑛
• Find location of X in (𝑎1 , 𝑎2 , … , 𝑎𝑛 ) if exists
1. i← 1 1
2. j← n 1
3. while i < j 𝑡𝑖
4. m ← (𝑖 + j)/2 𝑡𝑖 − 1
5. i𝑓 𝑥 > 𝑎m 𝑡𝑖 − 1
6. then i←m+1 (𝑡𝑖 −1)𝑡𝑚
7. 𝑒𝑙𝑠𝑒 j←m (𝑡𝑖 −1)(1 − 𝑡𝑚 )
8. if x = am 1
9. then loc = i 𝑡𝑎
10 𝑒𝑙𝑠𝑒 loc = 0 1-𝑡𝑎
9. return loc 1 37
 Computing T(I): Binary Search
• Binary search (Cont. )

𝑇 𝐼
= 4 + 𝑡𝑖 + 2 𝑡𝑖 − 1 + 𝑡𝑖 − 1 𝑡𝑚 + 𝑡𝑖 − 1 1 − 𝑡𝑚 + 𝑡𝑎 + (1 − 𝑡𝑎 )
𝑇 𝐼 = 5 + 𝑡𝑖 + 2𝑡𝑖 − 2 + 𝑡𝑖 − 1
𝑇 𝐼 = 𝜃(𝑡𝑖 )
Suppose that 𝑛 = 2𝑘 , since each iteration cuts the array into two
half, So the number of iterations in k.
𝒏=𝟖
𝑛 = 2𝑘 𝑰𝒕𝒆𝒓𝒂𝒕𝒊𝒐𝒏
log 𝑛 = log 2𝑘 𝟎
𝑘 = log 𝑛 𝟏
𝑇 𝐼 = 𝜃(log 𝑛)
𝟐

𝟑
 Computing T(I): Insertion Sort
• Insertion sort
• Let A be an array of length n = length(A) elements
• For 𝑗 = 2,3, … , 𝑛, let 𝑡𝑗 the number of times the while loop is
executed
1. for j← 2 to n 𝒏
2. do key ← A[j] 𝒏−𝟏
3. i ←j-1 𝒏−𝟏
4. while i > 0 and A i > key 𝒕𝒋
5. do A[i + 1] ← A[i] 𝒕𝒋 − 𝟏
6. i←i−1 𝒕𝒋 − 𝟏
3. A[i + 1] ← key 𝒏−𝟏

39
 Computing T(I): Linear Sort
• Insertion sort (Cont. )
𝑛 𝑛

𝑇 𝐼 = 𝑛 + 𝑛 − 1 + 𝑛 − 1 + ෍ 𝑡𝑗 + 2 ෍(𝑡𝑗 −1) + 𝑛 − 1
𝑗=2 𝑗=2
𝑛 𝑛 𝑛

𝑇 𝐼 = 4𝑛 − 3 + ෍ 𝑡𝑗 + 2 ෍ 𝑡𝑗 − ෍ 1
𝑗=2 𝑗=2 𝑗=2
𝑛

𝑇 𝐼 = 4𝑛 − 3 − 2 𝑛 − 1 + 3 ෍ 𝑡𝑗
𝑗=2
𝑛

𝑇 𝐼 = 2𝑛 − 1 + 3 ෍ 𝑡𝑗
𝑗=2

40
 Computing T(I): Linear Sort
• Insertion sort (Cont. )
Best case: Array is Sorted , then 𝑡𝑗 = 1
𝑛

𝐵 𝑛 = 2𝑛 − 1 + 3 ෍ 1
𝑗=2
𝐵 𝑛 = 2𝑛 − 1 + 3 𝑛 − 1 = 𝜃(𝑛)

Worst case: Array is Sorted Ascending and want to sort it in

descending order, then 𝑡𝑗 = 𝑗
𝑛

𝑇 𝑛 = 2𝑛 − 1 + 3 ෍ 𝑗
𝑗=2
𝑛 𝑛+1
𝑇 𝑛 = 2𝑛 − 1 + 3 −1
2
𝑇 𝑛 = 𝜃(𝑛2 ) 41
 Designing Algorithm
• 1- Incremental Approach
For Insertion Sort
- To solve the problem step-by-step in an incremental
fashion
- Having sorted the subarray 𝐴 1,2, … , 𝑗 − 1 , then
deal with subarray 𝐴 1,2, … , 𝑗 .
- The worst case for insertion sort is 𝜃(𝑛2 )
- We can get a better worst case using another
technique

42
 Designing Algorithm
• 2. Divide-and-Conquer Approach
• Algorithms are recursive. i.e. call them selves
recursively to deal with the problem.
• A teach level of recursion
1. Divide: the problem into sub problems
2. Conquer: the sub problems (Solve them)
1. Recursively
2. Straight forward, when the sub problem is small enough
3. Combine: The solution of the sub problems into a
solution of the original problem

43