Module I CST 306 - Algorithm Analysis and Design(S6 CSE)

Module I
 Introduction to Algorithm Analysis
o Characteristics of Algorithms
o Criteria for Analysing Algorithms
 Time and Space Complexity
o Best, Worst and Average Case Complexities
o Asymptotic Notations
 Big-Oh (O), Big- Omega (Ω), Big-Theta (Θ), Little-oh (o) and Little- Omega (ω) and
their properties.
 Classifying functions by their asymptotic growth rate
o Time and Space Complexity Calculation of simple algorithms
o Analysis of Recursive Algorithms:
 Recurrence Equations
 Solving Recurrence Equations
 Master’s Theorem
 Iteration Method
 Recursion Tree Method
 Substitution method

 Algorithm: An algorithm is a finite set of instructions that accomplishes a particular task.

 Characteristics of an Algorithm
o Input: Zero or more inputs are externally supplied.
o Output: At least one output is produced.
o Definiteness: Each instruction is clear and unambiguous.
 “add 6 or 7 to x” , “compute 5/0” etc. are not permitted.
o Finiteness: The algorithm terminates after a finite number of steps.
o Effectiveness: Every instruction must be very basic so that it can be carried out by a person
using only pencil and paper in a finite amount of time. It also must be feasible.

 Computational Procedures
o Algorithms those are definite and effective.
o Example: Operating system of a digital computer. (When no jobs are available, it does not
terminate but continues in a waiting state until a new job is entered.)
 Program: It is the expression of an algorithm in a programming language

 Recursive Algorithms
 A recursive function is a function that is defined in terms of itself.
 An algorithm is said to be recursive if the same algorithm is invoked in the body.
 Two types of recursive algorithms
 Direct Recursion: An algorithm that calls itself is direct recursive.
 Indirect Recursion: Algorithm A is said to be indirect recursive if it calls another
algorithm which in turn calls A.

 Performance Analysis(Criteria for Analysing Algorithms)

 Performance analysis depends on Space Complexity and Time Complexity

1 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
 Space Complexity
 The space complexity of an algorithm is the amount of memory it needs to run to
completion
 Space Complexity = Fixed Part + Variable Part
S(P) = c + SP , Where P is any algorithm
 A fixed part:
 It is independent of the characteristics of the inputs and outputs.
 Eg:
o Instruction space(i.e., space for the code)
o space for simple variables and fixed-size component variables
o space for constants
 A variable part:
 It is dependent on the characteristics of the inputs and outputs.
 Eg:
o Space needed by component variables whose size is dependent on the
particular problem instance being solved
o Space needed by referenced variables
o Recursion stack space.

 Time Complexity
 The time complexity of an algorithm is the amount of computer time it needs to run to
completion. Compilation time is excluded.
 Time Complexity = Frequency Count * Time for Executing one Statement
 Frequency Count  Number of times a particular statement will execute

 Eg1: Find the time and space complexity of matrix addition algorithm
Step/Execution Frequency Count Total Frequency Count
Algorithm mAdd(m,n,a,b,c) 0 0 0
{ 0 0 0
for i=1 to m do 1 m+1 m+1
for j=1 to n do 1 m(n+1) mn+m
c[i,j] := a[i,j] + b[i,j]; 1 mn mn
} 0 0 0
2mn + 2m +1
Time Complexity = 2mn + 2m + 1

Space Complexity = Space for parameters and Space for local variables
m1 n1 a[]mn b[]mn c[]mn i1 j1
Space complexity = 3mn + 4

2 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
 Eg2: Find the time and space complexity of recursive sum algorithm
Step/Execution Frequency Count Total Frequency Count
n≤0 n>0 n≤0 n>0
Algorithm RSum(a,n) 0 0 0 0 0
{ 0 0 0 0 0
if n ≤ 0 then 1 1 1 1 1
return 0 1 1 0 1 0
Else 0 0 0 0 0
return a[n] + RSum(a,n-1) 1 + T(n-1) 0 1 0 1 + T(n-1)
} 0 0 0 0 0
2 2 + T(n-1)
Time Complexity = T(n) = 2 if n<=0
2 + T(n-1) Otherwise
T(n) = 2 + T(n-1)
=2 + 2 + T(n-2)
=2 + 2 + 2+ T(n-3)
=2x3 + T(n-3)
. . .
=2xn +T(n-n)
=2n + 2

Space Complexity = Space for Stack

= Space for parameters + Space for local variables + Space for return address
For each recursive call the amount of stack required is 3
Space for parameters: a1 n1
Space for local variables: No local variables
Space for return address: 1
Total number of recursive call = n+1
Space complexity = 3(n+1)

 University Questions:
1. Discuss the time complexity of the following three functions
int fun1(int n)
{ if(n ≤ 1)
return n;
return 2xfun1(n-1);
}
int fun2(int n)
{ if(n ≤ 1)
return n;
return fun2(n-1)xfun2(n-1);
}

3 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
Answer:

4 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
2. Analyze the complexity of the following program
int fun3(int n)
{ if(n ≤ 1)
return n;
return fun3(n-1) + fun3(n-1);
}
Answer:

3. Analyze the complexity of the following program

main()
{ for(i=1; i<=n; i=i*2)
sum = sum + i + func(i);
}
void func(int m)
{ for(j=1; j<=m; j++)
Statement with O(1) complexity
}
Answer:

5 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
4. Analyse the complexity of the following function

void function(int n)
{
int count=0;
for(int i=n/2; i<=n; i++)
for(int j=1; j<=n; j=2*j)
for(int k=1; k<=n; k=k*2)
count++;
}

Answer:

5. Analyse the complexity of the following functions

function(int n)
{ if(n==1) return;
for(i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{ printf(“*”);
break;
}
}
void function(int n)
{ int i=1; s=1;
while(s<=n)
{ i++;
s+=i;
printf(“*”);
}
}

6 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
Answer:

6. Express the return value of the function “mystery” in ɵ notation

int mystery(int n)
{
int j=0,total=0;
for (int i=1;j<=n;i++)
{
++total;
j+=2*i;
}
return total;
}
Answer:

7 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
7. Find the time complexity of the given code segment
for(int i=1;i<=n;i++)
{ for(int j=i+1;j<=n;j++)
{
//code
}
}
Answer: The most frequently executing statement is the innermost code. During the
first iteration of outer loop that code will execute n-1 times. During the 2nd iteration of
outer loop that code will execute n-2 times and so on. During the last iteration it will
never execute.
So the frequency count of that code = (n-1) + (n-2) + …….. + 0
= (n-1)n/2 = (n2-n)/2
2
Time Complexity = O(n )

8. Find the time complexity of the given code segment

for(int i=1;i<=n;i++)
{
for(int j=1;j<=i*i;j++)
{
for(int k=1;k<=n/2;k++)
{
//code
}
}
}
Answer: The 1st loop will successfully execute n times
The 2nd loop will successfully execute 12 + 22 + 32 + . . . . . + n2 times
The 3rd loop will successfully execute (12 + 22 + 32 + . . . . . + n2) n /2 times
So the frequency count of innermost code = (12 + 22 + 32 + . . . . . + n2) n /2
= [n(n+1)(2n+1)/6] n /2
4
Time Complexity = O(n )

9. Find the time complexity of the given code segment

for(int i=1;i<=n;i++)
{ for(int j=1;j<=i;j++)
{ for(int k=1;k<=100;k++)
{
//code
}
}
}
Answer: The 1st loop will successfully execute n times
The 2nd loop will successfully execute 1 + 2 + 3 + . . . . . + n times
The 3rd loop will successfully execute (1 + 2 + 3 + . . . . . + n)100 times
So the frequency count of innermost code = (1 + 2 + 3 + . . . . . + n)100
= [n(n+1)/2] 100
2
Time Complexity = O(n )

8 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
10. Consider the following C function
int check(int n)
{
int i,j;
for (i=1;i<=n;i++)
{
for (j=1;j<n;j+=i)
{
printf("%d",i+j);
}
}
}
Find the time complexity of check in terms of ɵ notation

 Best Case, Worst Case and Average Case Complexity

 In certain case we cannot find the exact value of frequency count. In this case we have 3 types
of frequency counts
 Best Case : It is the minimum number of steps that can be executed for a given parameter
 Worst Case: It is the maximum number of steps that can be executed for a given parameter
 Average Case: It is the average number of steps that can be executed for a given parameter
 Example: Linear Search
 Best Case: Search data will be in the first location of the array.
 Worst Case: Search data does not exist in the array
 Average Case: Search data is in the middle of the array.
Best Case Worst Case Average Case
S/E FC TFC S/E FC TFC S/E FC TFC
Algorithm Search(a,n,x) 0 0 0 0 0 0 0 0 0
{ 0 0 0 0 0 0 0 0 0
for i:=1 to n do 1 1 1 1 n+1 n+1 1 n/2 n/2
if a[i] ==x then 1 1 1 1 n n 1 n/2 n/2
return i; 1 1 1 1 0 0 1 1 1
return -1; 1 0 0 1 1 1 1 0 0
} 0 0 0 0 0 0 0 0 0
3 2n + 2 n+1
Best Case Complexity = 3 = Ω(1)
Worst Case Complexity = 2n + 2 = O(n)
Average Case Complexity = n+1 = Ɵ(n)
 University Questions:
1. Define the terms best case, average case and worst case complexities.
2. Discuss the best case and worst case time complexity of linear search algorithm
3. Determine the Best case and Worst case time complexity of the following function
void fun(int n, int arr[])
{
int i=0; j=0;
for(;i<n;++i)
while(j<n && arr[i]< arr[j])
j++;
}

9 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
4. Illustrate best case, average case and worst case complexity of Insertion sort algorithm.
Answer:
Algorithm InsertionSort(A,n)
{
for i=1 to n-1 do
{
j=i
while j>0 and A[j-1] > A[j] do
{
Swap(A[j], A[j-1])
j=j-1
}
}
}

Best case complexity: Best case situation occurs when the array itself is in sorted order. In
this case the while loop will not execute successfully. So the time complexity is
proportional to number of times the for loop will execute. It will execute O(n) time.
The best case time complexity = Ω(n)

Worst case complexity: Worst case situation occurs when the array itself is in reverse
sorted order. In this case the while loop will execute 1+2+3+ . .. .+(n-1)=n(n+1)/2 times.
The time complexity is proportional to number of times the while loop will execute. It will
execute O(n2) time.
The worst case time complexity = O(n2)

Average case complexity: Average case situation occurs when the while loop will iterate
half of its maximum iterations. In this case the while loop will execute [1+2+3+ . .. .+(n-
1)]/2=n(n+1)/4 times.
The time complexity is proportional to number of times the while loop will execute. It will
execute O(n2) time.
The average case time complexity = Ɵ(n2)

5. Write an algorithm for insertion sort. Calculate the worst case time complexity of insertion
sort.

 Asymptotic Notations
 It is the mathematical notations to represent frequency count. 5 types of asymptotic notations
 Big Oh (O)
 The function f(n) = O(g(n)) iff there exists 2 positive constants c and n0 such that
0 ≤ f(n) ≤ c g(n) for all n ≥ n0
 It is the measure of longest amount of time taken by an algorithm(Worst case).
 It is asymptotically tight upper bound
 O(1) : Computational time is constant
 O(n) : Computational time is linear
 O(n2) : Computational time is quadratic
 O(n3) : Computational time is cubic
 O(2n) : Computational time is exponential

10 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
 Omega (Ω)
 The function f(n) = Ω (g(n)) iff there exists 2 positive constant c and n0 such that
f(n) ≥ c g(n) ≥ 0 for all n ≥ n0
 It is the measure of smallest amount of time taken by an algorithm(Best case).
 It is asymptotically tight lower bound

 Theta (Ɵ)
 The function f(n) = Ɵ (g(n)) iff there exists 3 positive constants c1, c2 and n0 such that
0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n) for all n ≥ n0
 It is the measure of average amount of time taken by an algorithm(Average case).

 Little Oh (o)
 The function f(n) = o(g(n)) iff for any positive constant c>0, there exists a constant n0>0
such that 0 ≤ f(n) < c g(n) for all n ≥ n0
 It is asymptotically loose upper bound

g(n) becomes arbitrarily large relative to f(n) as n approaches infinity

 Little Omega (ω)

 The function f(n) = ω(g(n)) iff for any positive constant c>0, there exists a constant
n0>0 such that f(n) > c g(n) ≥ 0 for all n ≥ n0
 It is asymptotically loose lower bound

f(n) becomes arbitrarily large relative to g(n) as n approaches infinity

 Examples:
1. Find the O notation of the following functions
a) f(n) = 3n + 2
3n + 2 ≤ 4 n for all n≥2
Here f(n)= 3n + 2 g(n)=n c=4 n0=2
Therefore 3n + 2= O(n)
b) f(n) = 4n3 + 2n + 3
4n3 + 2n + 3 ≤ 5 n3 for all n≥2
Here f(n)= 4n3 + 2n + 3 g(n)= n3 c=5 n0=2
3 3
Therefore 4n + 2n + 3= O(n )
c) f(n) = 2n+1
2n+1 ≤ 2 2n for all n≥1

11 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
n+1 n
Here f(n)= 2 g(n)= 2 c=2 n0=1
Therefore 2n+1 = O(2n)
d) f(n) = 2n + 6n2 + 3n
2n + 6n2 + 3n ≤ 7 2n for all n≥5
Here f(n)= 2n + 6n2 + 3n g(n)= 2n c=7 n0=5
Therefore 2n + 6n2 + 3n = O(2n)
2
e) f(n) = 10n + 7
f) f(n) = 5n3 + n2 + 6n + 2
g) f(n) = 6n2 + 3n + 2
h) f(n) = 100n + 6

2. Is 22n = O(2n)? (Univ Question)

22n ≤ c 2n
2n ≤ c
There is no value for c and n0 that can make this true.
Therefore 22n != O(2n)

3. Is 2n+1 = O(2n)? (Univ Question)

n+1 n
2 ≤c2
2x2n ≤ c 2n
2≤c
2n+1 ≤ c 2n is True if c=2 and n≥1.
Therefore 2n+1 = O(2n)
4. Let f(n) = 3n3 + 2n2 + 3 for an algorithm. Let g(n) = n3. Prove that f(n) of this algorithm is
in O(n3). (Univ Question)
3 2
Answer: f(n) = 3 n + 2 n + 3
Assume that g(n)= n3 and c=10
As per O notation 0<= f(n) <=c g(n) for all n>=no
0<=3 n3 + 2 n2 + 3<=c n3 for all n>=1
Therefore, f(n) = O(g(n)) = O(n3)

5. What is the smallest value of n such that an algorithm whose running time is 100n2 runs
faster than an algorithm whose running time is 2n on the same machine? (Univ Question)

6. Find the Ω notation of the following functions

a) f(n) = 27 n2 + 16n + 25
27 n2 + 16n + 25 ≥ 27 n2 for all n ≥ 1
Here c=27 n0=1 g(n)= n2
27 n2 + 16n + 25 = Ω(n2)
b) f(n) = 5 n3 + n2 + 3n + 2
5 n3 + n2 + 3n + 2 ≥ 5 n3 for all n ≥ 1
Here c=5 n0=1 g(n)= n3
5 n3 + n2 + 3n + 2= Ω(n3)
c) f(n) = 3n + 6n2 + 3n
3n + 6n2 + 3n ≥ 5.3n for all n ≥ 1
Here c=5 n0=1 g(n)= 3n
3 + 6n + 3n = Ω(3n)
n 2

12 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
n
d) f(n) = 4 2 + 3n
e) f(n) = 3n + 30
f) f(n) = 10 n2 + 4n + 2

7. Find the Ɵ notation of the following functions

a) f(n) = 3n + 2
3n + 2 ≤ 4 n for all n≥2
3n + 2 = O(n)

3n + 2 ≥ 3 n for all n≥1

3n + 2 = Ω (n)

3 n ≤ 3n + 2 ≤ 4 n for all n≥2

3n + 2 = Ɵ(n)

b) f(n) = 3 2n + 4n2 + 5n + 2
3x2n + 4n2 + 5n + 2 ≤ 10x2n for all n≥1
3x2n + 4n2 + 5n + 2 = O(2n)

3x2n + 4n2 + 5n + 2 ≥ 3x2n for all n≥1

3x2n + 4n2 + 5n + 2 = Ω (2n)

3x2n ≤ 3x2n + 4n2 + 5n + 2 ≤ 10 2n for all n≥1

3x2n + 4n2 + 5n + 2 = Ɵ(2n)

c) f(n) = 2 n2 + 16
d) f(n) = 27n2 + 16

 Common Complexity Functions

 Constant Time
 An algorithm is said to be constant time if the value of f(n) is bounded by a value that does
not depend on the size of input.
 Computational time is constant
 Eg: O(1)
 Logarithmic Time
 An algorithm is said to be logarithmic time if f(n) = O(log n)
 Linear Time
 If f(n) = O(n), then the algorithm is said to be linear time .
 Quadratic Time
 If f(n) = O(n2), then the algorithm is said to be quadratic time .
 Polynomial Time
 If f(n) = O(nk), then the algorithm is said to be polynomial time .
 Exponential Time
 If f(n) = O(2n), then the algorithm is said to be exponential time .
 Factorial Time
 If f(n) = O(n!), then the algorithm is said to be factorial time

13 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
 Running Time Comparison (Classifying functions by their asymptotic growth rate)
 Logarithmic functions are very slow
 Exponential functions and factorial functions are very fast growing
n log n n n log n n2 n3 2n n!
10 3.3 10 3.3 x 10 102 103 103 3.6 x 1060

102 6.6 102 6.6 x 102 104 106 1.3 x 1030 9.3 x 10157
. .
103 10 103 10 x 103 106 109 . .
. .
104 13 104 13 x 104 108 1012 . .
. .
105 17 105 17 x 105 1010 1015 . .
. .
106 20 106 20 x 106 1012 1018
O(1) < O(log n) < O(n) < O(n log n) < O(nk) < O(2n) < O(n!)

 Properties of Asymptotic Notations

 Reflexivity
 f(n) = O(f(n))
 f(n) = Ω(f(n))
 f(n) = Ɵ(f(n))
 Symmetry
 f(n) = Ɵ(g(n)) if and only if g(n) = Ɵ(f(n)
 Transpose Symmetry
 f(n) = O(g(n)) if and only if g(n) = Ω(f(n))
 f(n) = o(g(n)) if and only if g(n) = ω(f(n))
 Transitivity
 f(n) = O(g(n)) and g(n) = O(h(n)) imply f(n) = O(h(n))
 f(n) = Ω(g(n)) and g(n) = Ω(h(n)) imply f(n) = Ω(h(n))
 f(n) = Ɵ(g(n)) and g(n) = Ɵ(h(n)) imply f(n) = Ɵ(h(n))
 f(n) = o(g(n)) and g(n) = o(h(n)) imply f(n) = o(h(n))
 f(n) = ω(g(n)) and g(n) = ω(h(n)) imply f(n) = ω(h(n))

 University Questions:
1. Explain asymptotic notations in algorithm analysis
2. Define Big Oh, Big Omega and Theta notations and illustrate them graphically.
3. What do you meant by asymptotic growth rate? Define Big Oh, Big Omega and Theta
notations
4. Define asymptotic notation. Arrange the following functions in increasing order of
asymptotic growth rate. n3 , 2n , log n 3 , 2100, n2 log n, nn, log n, n0.3, 2log n
Answer : 2 < log n < log n < n0.3 < n2 log n < n3 < 2log n < 2n < nn
100 3

14 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
 Recurrence Relations
 A recurrence is an equation or inequality that describes a function in terms of its values on
smaller inputs.
 There are several methods for solving recurrence relation
 Iteration Method
 Recursion tree Method
 Substitution Method
 Master’s Method

 Iteration Method

 Solve the following recurrence relation using Iteration method.

1. T(n) = 1 + T(n-1)
T(n) = 1 + T(n-1)
=1 + 1 + T(n-2) = 2 + T(n-2)
= 2 + 1 + T(n-3) = 3 + T(n-3)
. . . .
= k + T(n-k) kth term
Assume n-k = 1  k = n-1
T(n) = n-1 + T(n-(n-1))
= n-1 + T(1) = O(n) + O(1) = O(n)

2. T(2k) = 3 T(2k-1) + 1 (Univ Question)

T(1) = 1
Answer:
T(2k) =1+ 3T(2k-1)
=1+3[1+ 3T(2k-2)] = 1+3+32T(2k-2)
= 1+3+32 [1+3T(2k-3)]= 1+3+32+33T(2k-3)
……………….
= 1+3+32+….. +3n-1+3nT(2k-n) nth term
Assume that 2k-n=1  2k/2n=1  2k=2n  k=n
k 2 n-1 n k-n n n
T(2 ) = 1+3+3 +…. +3 +3 T(2 ) = [(3 -1)/(3-1)]+3 T(1)
= (3n/2)-(1/2)+3n
= (3/2) 3n-(1/2)
= (3/2) 3k-(1/2)
=O(3k)

3. T(n) =2T(n/2)+2 if n>2 (Univ Question)

=1 if n=2
Answer:
T(n) = 2 + 2T(n/2)
=2 + 2[2+2T(n/22)] = 2+22+22T(n/22)
= 2+22+22[2+2T(n/23)] = 2+22+23+23T(n/23)
……………………..
= 2+22+23+……… +2k + 2kT(n/2k) kth term

15 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
k
Assume that n/2 =2
T(n) =2[1+2+2 +2 +……… +2k-1 ] + 2kT(n/2k)
2 3

=2[2k-1] + 2kT(2) = 2x2k-2 + 2k

= 3x2k-2 = 3x(n/2)-2

4. T(n) = 2 T(n/2) + n T(1)=1 (Univ Question)

Answer:
T(n) = n + 2 T(n/2)
= n + 2 [(n/2)+ 2 T(n/22)] = 2n + 22T(n/22)
= 2n + 22 [(n/22)+2T(n/23)]= 3n + 23T(n/23)
………………………….
=k n + 2kT(n/2k) kth term
Assume that n/2k=1  2k=n  k=log2(n)
T(n) =nlog2 (n) + nT(1)
=nlog2 (n) + n
=O(nlog2(n))

5. T(n) = 2 if n=1 (Univ Question)

T(n) = 2T(n/2) + 2n + 3 Otherwise
Answer:
T(n) = 3 + 2n + 2T(n/2)
= 3 + 2n + 2[3+2(n/2)+2T(n/22)]
=3+2x3+2x2n+22T(n/22)
=3+2x3+2x2n+22 [3+2(n/22)+2T(n/23)]
= 3+2x3+22x3+3x2n+23T(n/23)
……………………………..
= [3+2x3+22x3+…. +2k-1x3]+[kx2n]+2kT(n/2k) kth term
Assume that n/2k=1  2k=n  k=log2(n)
T(n) =3[20+21+22+…+2k -1]+2nlog2(n) + nT(1)
=3[(2k -1)/(2-1)] +2nlog2(n) + 2n
= 3(n -1) +2nlog2(n) + 2n
= 5n -3 +2nlog2(n) = O(nlog2(n))

6. T(n) = 3 T(n/3) + n, T(1) = 1 (Univ Question)

Answer:
T(n) = n + 3T(n/3)
= n + 3[(n/3)+3T(n/32)] = n + n + 32T(n/32)
= 2 n+32 [(n/32) +3T(n/33)]
= 3 n + 33 T(n/33)
……………………
= k n + 3k T(n/3k) kth term
Assume n/3k= 1  3k = n  k = log3(n)
T(n) = n log3(n) + n T(1)
= n log3(n) + n = O(n log3(n) )

16 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
2
7. T(n) = 2 T(n/2) + n (Univ Question)
Answer:
T(n) = n2 + 2T(n/2)
= n2 + 2[(n/2) 2+2T(n/22)] = n2+n2/2 + 22 T(n/22)
= n2 + n2/2 + 22 [(n/22) 2+2T(n/23)]
= n2+n2/2 + n2/22 +23 T(n/23)
……………………
= n2[1+ (1/2) + (1/2)2 + …. + (1/2)k-12 ] + 2k T(n/2k) kth term
Assume n/2k= 1  2k = n  k = log2(n)
T(n) = n2 [(1-(1/2)k) / (1-(1/2))] + n T(1)
= 2 n2 [ 1-(1/2k)] + n = 2 n2 [ 1-(1/2log n)] + n
= 2 n2 [ 1-(1/nlog 2)] + n = 2 n2 [ 1-(1/n)] + n
= 2 n2 - 2n+ n
= O(n2)

8. T(n) = T(n/3) + n
Answer:
T(n) = n + T(n/3)
= n + [(n/3) + T(n/32)] = n + (n/3) + T(n/32)
=n+(n/3)+[(n/32)+T(n/33)]=n+(n/3)+(n/32)+T(n/33)
……………………
= n+(n/3)+(n/32)+ …. +(n/3k-1)+T(n/3k) kth term
Assume n/3k= 1  3k = n  k = log3(n)
T(n) = n[1+(1/3)+(1/3) 2+….+(1/3) k-1] + T(n/3k)
3
= n [ [ 1- (1/3)k] / [ 1-(1/3)] ] + T(1) = 2n [1-(1/3k)] + T(1)
3 1 3 3
= 2n [1- 𝑛 ] +1 = 2n - 2 + 1
=O(n)

9. T(n) = 3 T(n/4) + n
Answer:
T(n) = n + 3T(n/4)
= n + 3[(n/4)+3T(n/42)] = n + (3/4)n+32T(n/42)
= n + (3/4)n+32[(n/4) 2+3T(n/43)]
= n + (3/4)n+(3/4) 2n+33T(n/43)
……………………
= n + (3/4)n+(3/4) 2n+ …. +(3/4) k-1n+3kT(n/4k) kth term
Assume n/4k= 1  4k = n  k = log4(n)
T(n) = n[1+(3/4) +(3/4) 2+….+(3/4) k-1] + 3kT(1)
= n [[ 1- (3/4)k] / [ 1-(3/4)] ] + 3k x 1
= 4 n [ 1 – (3k/4k)] + 3k alogc(b) =blogc(a)
= 4 n [ 1 - (3log4n /n)] + 3log4n
= 4 n [ 1 - (nlog43 /n)] + nlog43

17 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
=4n–4 nlog43 + nlog43 =4n–3 nlog43
=O(n)

10. T(n) = T(n/2) + 1

Answer:
T(n) = 1 + T(n/2)
= 1 + [1+ T(n/22)] = 2+ T(n/22)
= 2+ [1+ T(n/23)] = 3+ T(n/23)
……………………
= k + T(n/2k) kth term
Assume n/2k= 1  2k = n  k = log2(n)
T(n) = log2(n) + T(1) = log2(n) + 1
= O(log2(n) )

11. T(n) = 4 T(n/2) + n2

Answer:
T(n) = n2 + 4T(n/2)
= n2+4[(n/2)2 +4T(n/ 22)] = 2n2+42T(n/ 22)
= 2n2+42[(n/ 22)2 +4T(n/ 23)] = 3n2+43T(n/ 23)
……………………
= kn2+4kT(n/ 2k) kth term
Assume n/2k= 1  2k = n  k = log2(n)
T(n) = n2log2(n) +4k T(1) 4k =n2
= n2log2(n) + n2
= O(n2log2(n))
12. T(n) = 4 T(n/3) + n
Answer:
T(n) = n + 4T(n/3)
= n + 4[(n/3)+4T(n/32)] = n + (4/3)n+42T(n/32)
= n + (4/3)n+42 [(n/3) 2+4T(n/33)]
= n + (4/3)n+(4/3) 2n+43T(n/33)
……………………
= n + (4/3)n+(4/3) 2n+ …. +(4/3) k-1n+4kT(n/3k) kth term
Assume n/3k= 1  3k = n  k = log3(n)
2 k-1 k
T(n) = n[1+(4/3) +(4/3) +….+(4/3) ] + 4 T(1)
= n[((4/3)k-1)/((4/3)-1)] + 4k
= n[((4k/3k) -1)/(1/3)] + 4k
= 3n[((4log3n/3log3n) -1)] + 4log 3n
= 3n[((nlog34/nlog33) -1)] + nlog 34
= 3n[((nlog34/n) -1)] + nlog 34
= 3n log34 -3n + nlog 34
= 4n log34 -3n
= O(nlog34 )

18 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
 Recursion Tree Method
 It is the pictorial representation of iteration method, which is in the form of a tree.
 Solve the following recurrence relation using Recursion Tree method.
1. T(1) = 1 (Univ Question)
T(n) = 3 T(n/4) + cn2
Answer:

T(n) = cn2 + (3/16) cn2 + (3/16) 2 cn2 + …..+ (3/16) k cn2

= cn2[1 + (3/16) + (3/16) 2 + …..+ (3/16) k]
≤ cn2[1 + (3/16) + (3/16) 2 + ……….]
= cn2[1/(1- (3/16))]
= (16/13) cn2
=O(n2)

2. T(n) = 3T(n/4) + n2 (Univ Question)

Answer:

19 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)

T(n) = n2 + (3/16) n2 + (3/16) 2 n2 + …..+ (3/16) k n2

= n2[1 + (3/16) + (3/16) 2 + …..+ (3/16) k]
≤ n2[1 + (3/16) + (3/16) 2 + ……….]
= n2[1/(1- (3/16))]
= (16/13) n2
=O(n2)

3. T(n) = 2 T(n/10) + T(9n/10) + n (Univ Question)

Assume constant time for small value of n
Answer:

Assume that 9kn/10k=1  (10/9) k=n  k=log(10/9) n

T(n) =n+(11/10)n+(11/10)2n+……..+(11/10)kn
=n[1+(11/10)+(11/10)2+……..+(11/10)k]
=n[ [(11/10)k+1 -1] / [(11/10)-1] ]
=10n[ [(11/10)x(11/10) k] -1]
=10n[ [(11/10)x(11/10) log10/9 n] -1]
=10n[ [(11/10) x n log10/9(11/10) ] -1]
=10n[ [(11/10) x n1 ] -1]
=11n2 -10n =O(n2)
Longest path: Rightmost path
Longest Path length:
9kn/10k=1 , where k is the length of the longest path
(10/9) k=n
k=log(10/9) n
Shortest path: Leftmost path
Shortest Path length:
n/10k=1 , where k is the length of the shortest path
10k=n
k=log10 n

20 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
4. T(n) = T(n/3) + T(2n/3) + n, where n>1 (Univ Question)
T(n) = 1, Otherwise
Answer:

Assume that 2kn/3k = 1  (3/2)k = n  k= log(3/2) n

T(n) = (k+1) n
= (log(3/2) n + 1) n
= n log(3/2) n + n
= O(n log(3/2) n)

Longest path: Rightmost path

Longest Path length:
2kn/3k = 1 , where k is the length of the longest path
(3/2) k=n
k=log(3/2) n

Shortest path: Leftmost path

Shortest Path length:
n/3k=1 , where k is the length of the shortest path
3k=n
k=log3 n

5. T(n) = T(n/3) + T(2n/3) + c n (Univ Question)

6. T(n) = 2 T(n/2) + n where n>1 (Univ Question)

0 Otherwise

21 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
2
7. T(n) = 2T(n/2) + n where n>1 (Univ Question)
0 otherwise
Answer:

Assume n/2k=1  2k=n  k=log2 n

T(n) = n2+(n2 /2) +(n2 / 22)+……..+(n2 / 2k)

= n2[1+(1/2)+(1/2) 2+. . . . . .+ (1/2) k]
= n2 [ [1-(1/2) k+1] / [1-(1/2)] ]
= 2n2 [ 1- (1/2)x(1/2) k]
= 2n2 [ 1- (1/2)x(1/2k)]
= 2n2 [ 1- (1/2)x(1/n)]
= 2n2 – n
= O(n2)

8. T(n) = 3 T(n/3) + c n
Answer:

Assume that n/3k=1  3k=n  k=log3(n)

T(n) = (k+1)cn
=(log3(n)+1)cn
=cn log3(n)+cn
=O(n log3(n))

22 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
9. T(n) = 4 T(n/2) + n
Answer:

Assume n/2k=1  2k=n  k=log2 n

T(n) = n+2n + 22 n+……..+2k n

= n[1+2+22+. . . . . .+ 2 k]
= n[ [2 k+1-1] / [2-1] ]
= n [2x2 k-1]
= n [ 2n-1]
= 2n2 –n
= O(n2)

10. T(n) = 2 T(n-1) + c

Answer:

T(n) = c+2c + 22 c+……..+2n-1 c

= c[1+2+22+. . . . . .+ 2 n-1]
= c[ [2 n-1] / [2-1] ]
= c [2 n-1]
= c 2n –c
= O(2n)

23 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
2
11. T(n) = 8 T(n/2) + n
Answer:

Assume that n/2k = 1  2k=n  k=log2 n

T(n) = n2+2n2 + 22 n2+……..+2k n2
= n2 [1+2+22+. . . . . .+ 2 k]
= n2 [ [2 k+1-1] / [2-1] ]
= n2 [2x2 k-1]
= n2 [ 2n-1]
= 2n3 – n2
= O(n3)

12. T(n) = 3T(n/2) + n

Answer:

Assume that n/2k = 1  2k=n  k=log2 n

T(n) = n+(3/2)n+ (3/2)2n+……..+ (3/2)kn

= n[1+(3/2)+(3/2)2+. . . . . .+ (3/2) k]
= n[ [ (3/2) k+1 - 1] / [(3/2)-1] ]

24 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
k
= n[[(3/2) (3/2) - 1] / [1/2] ]
= 2n[(3/2) (3 k /2 k) - 1]
= 2n[(3/2) (3 log2n /2 log2n) - 1]
= 2n[(3/2) (n log23 /n log22) - 1]
= 2n[(3/2) (n log23 /n) - 1]
= 3n log23 – 2n
= O(n log23 )

13. T(n) = T(n/2) + n2

Answer:

Assume that n/2k = 1  2k=n  k=log2 n

T(n) = n2+n2/4 + n2/42+……..+ n2/4k

= n2 [1+(1/4)+(1/4)2+. . . . . .+ (1/4) k]
= n2[ [1- (1/4) k+1] / [1-(1/4)] ]
= n2[ [1- (1/4) (1/4) k] / [3/4] ]
= (4/3) n2[ 1- (1/4) (1/4 log n )]
= (4/3) n2[ 1- (1/4) (1/n log 4 )]
= (4/3) n2[ 1- (1/4) (1/n2)]
= (4/3) n2- (1/3)
= O(n2)

25 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
 Master’s Method
n
T(n) = aT(b ) + 𝜃(𝑛𝑘 𝑙𝑜𝑔𝑝 𝑛)
a≥1 b>1 k≥0 and p is a real number

1. If a>𝑏 𝑘 then T(n) = 𝜃(n (log ba))

2. If a=𝑏 𝑘
a. If p>-1 then T(n)= 𝜃(n(log b a) logp+1(n))
b. If p=-1 then T(n)= 𝜃(n(log b a) log(log n)
c. If p<-1 then T(n)= 𝜃(n(log b a))
3. If a<𝑏 𝑘
a. If p≥0, then T(n)= 𝜃(nk logp(n))
b. If p<0, then T(n)= 𝜃(nk)

 State Master’s theorem (Univ Question)

 Solve the following recurrence relation using Master’s method.
1. T(n) = 3 T(n/2) + n2 (Univ Question)
Answer:
T(n) = 3 T(n/2) + n2
a=3 b=2 n2 =Ɵ (n2 log0(n)) k=2 p=0
k 2
b =2 = 4
Here a< bk and p≥0
T(n) = Ɵ(nk logp(n))
= Ɵ(n2 log0(n))
= Ɵ(n2)
2. T(n) = 2 T(n/2) + n log n (Univ Question)
Answer:
T(n) = 2 T(n/2) + n log n
a=2 b=2 n log n =Ɵ (n1 log1(n)) k=1 p=1
k 1
b =2 = 2
Here a= bk and p>-1
T(n) = Ɵ(n(log b a) logp+1(n))
= Ɵ(n(log 2 2) log2(n))
= Ɵ(nlog2(n))

3. T(n) = 2 T(n/4) + 𝑛 (Univ Question)

Answer:

26 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
2
4. T(n) = 7 T(n/2) + n (Univ Question)
Answer:
T(n) = 7T(n/2) + n2
a=7 b=2 n2=Ɵ (n2 log0(n)) k=2 p=0
bk =22 = 4
Here a> bk
T(n) = Ɵ(n(log b a))
= Ɵ(n(log 2 7))

5. T(n) = 2 T(n/2) + n/log n

Answer:
T(n) = 2 T(n/2) + (n/log n)
a=2 b=2 (n/log n) =Ɵ (n1 log-1(n)) k=1 p=-1
bk =21 = 2
Here a= bk and p=-1
T(n) = Ɵ(n(log b a) log(log n))
= Ɵ(n(log 2 2) log(log n))
= Ɵ(n log(log n))

6. T(n) = 3 T(n/4) + n log n (Univ Question)

7. T(n) = 9 T(n/3) + n (Univ Question)
8. T(n) = 8 T(n/2) + 100 n2 (Univ Question)
9. T(n) = 2 T(n/2) + 10 n (Univ Question)

10. T(n) = 2n T(n/2) + nn (Univ Question)

Answer:
T(n) = 2nT(n/2) + nn
As per master’s theorem, a≥1. Here a=2n
So we cannot solve this relation using Master’s Method.

11. T(n) = 4 T(n/2) + n2

12. T(n) = T(n/2) + n2
13. T(n) = 16 T(n/4) + n
14. T(n) = 2 T(n/4) + n0.51
15. T(n) = 0.5 T(n/2) + 1/n
16. T(n) = 6 T(n/3) + n2 log n
17. T(n) = 64 T(n/8) - n2 log n
18. T(n) = 7 T(n/3) - n2
19. T(n) = 4 T(n/2) + log n
20. T(n) = 2 T(n/2) + log n
21. T(n) = 2 T(n/2) + 𝑛
22. T(n) = 3 T(n/2) + n
23. T(n) = 3 T(n/3) + 𝑛
24. T(n) = 4 T(n/2) + c n
25. T(n) = T(2n/3) + 1
26. T(n) = 2 T(n/2) + n log n

27 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
2
27. T(n) = 8 T(n/2) + Ɵ (n )
28. T(n) = 2 T(n/4) + 1
29. T(n) = 2 T(n/4) + n
30. T(n) = 2 T(n/4) + n2
31. T(n) = T(n/2) + Ɵ (1)
32. T(n) = 4 T(n/2) + n2 log n

 Substitution Method
 The substitution method for solving recurrences comprises two steps
1. Guess the form of the solution
2. Use mathematical induction to find the constant & show that the solution works.
 This method is powerful, but we must be able to guess the form of the answer in order to
apply it.
 Example:
1. Give the general idea of the substitution method for solving recurrences. Solve the
following recurrences using substitution method
T(n) = 2 T(n/2) + n T(1) = 1 (Univ Question)

Answer:
Guess that T(n) = O(n log n)
As per O notation definition T(n) <= c n log n
By mathematical induction
If n=1, T(1) <= c x 1 x log 1  1 <= 0 It is false
If n=2, T(2) <= c x 2 x log 2  2 T(1) + 2 <= 2 c  4 <= 2c It is true
If n=3, T(3) <= c x 3 x log 3  2 T(1) + 3 <= c x 3 x log 3
5 <= 3 c log 3 It is true
This relation is true when n= 2, 3, 4 . . . . ., k
T(k) <= c k log k, where 2<= k <= n
T(n/2) <= c (n/2) log (n/2) 1

The recurrence relation is

T(n) = 2 T(n/2) + n
Apply equation number 1
T(n) <= 2 c (n/2) log (n/2) + n
<= c n log (n/2) + n
<= c n log n – c n log 2 + n
<= c n log n
Therefore T(n) = O(n log n)

2. Solve the following recurrence relation using substitution method

T(n) = 1 if n=1
2T(n/2) + 1 Otherwise

Answer:
Guess that T(n) = O(n)
As per O notation definition T(n) <= c n
By mathematical induction
If n=1, T(1) <= c x 1  1 <= c It is true

28 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)
If n=2, T(2) <= c x 2  2 T(1) + 1 <= 2 c  3 <= 2c It is true
This relation is true when n= 1, 2, 3, . . . . ., k
T(k) <= c k , where 2<= k <= n
T(n/2) <= c (n/2) 1

The recurrence relation is

T(n) = 2 T(n/2) + 1
Apply equation number 1
T(n) <= 2 c (n/2) + 1
<= c n + 1
<= c n
Therefore T(n) = O(n)

3. Solve the following recurrences using substitution method

T(n) = 2 T(n/2) + k n T(1) = 1

Answer:
Guess that T(n) = O(n log n)
As per O notation definition T(n) <= c n log n
By mathematical induction
If n=1, T(1) <= c x 1 x log 1  1 <= 0 It is false
If n=2, T(2) <= c x 2 x log 2  2 T(1) +kx2 <= 2 c
 2 +2 k <= 2c It is true
This relation is true when n= 2, 3, 4 . . . . ., k
T(k) <= c k log k, where 2<= k <= n
T(n/2) <= c (n/2) log (n/2) 1

The recurrence relation is

T(n) = 2 T(n/2) + k n
Apply equation number 1
T(n) <= 2 c (n/2) log (n/2) + k n
<= c n log (n/2) + k n
<= c n log n – c n log 2 + k n
<= c n log n – c n + k n
<= c n log n
Therefore T(n) = O(n log n)

29 CS KTU Lectures
Module I CST 306 - Algorithm Analysis and Design(S6 CSE)

 Arithmetic Progression
 Series: a , a+d , a+2d , a+3d . . . . . . . . . . a+(n-1)d
 nth term: a+(n-1)d
 sum of first n terms:

 Geometric progression
 Series: a , ar , ar2 , ar3 . . . . . . . . . . arn-1
 nth term: arn-1
 sum of first n terms:

 sum of infinite terms:

 Logarithm related equations

 x log a b = b log a x

 log a a = 1

 if x k = n , then k = log k n

30 CS KTU Lectures