CS212: Design & Analysis of Algorithms 3rd Semester
Lecture 3: August 7
Instructor: Prof. Prateek Vishnoi Indian Institute of Technology, Mandi
Case Analysis for any algorithm
Best Case
Minimum time required for an output. Formally, we calculate the lower bound on the running time of an
algorithm.
Average Case
Time required to output for average number of inputs. In average case analysis, we take all possible inputs
and calculate the average computing time for all of the inputs.
Worst Case
Formally, we calculate the upper bound on the running time of an algorithm.
Recurrence Relations
There are basically three methods to solve a recurrence relation, however at heart we are doing the same at
each method. One more assumption in this course is n is always non-negative.
Substitution Method
Idea : Reduce the problem into subproblem in order to take it close to the exit condition.
Ex 1.
(
T (n − 1) + c if n > 1
T (n) =
1 if n = 1
3-1
3-2 Lecture 3: August 7
Sol :=
T (n) = T (n − 1) + c
Substitute the value of T (n − 1)
T (n) = T (n − 2) + 2c
Substitute the value of T (n − 2)
T (n) = T (n − 3) + 3c
..
.
After k steps
T (n) = T (n − k) + kc
By putting n = (k − 1) we get,
T (n) = 1 + (n − 1)c = Θ(n)
Ex. 2 :
(
2T ( n2 ) + c if n > 1
T (n) =
1 if n = 1
Sol :
T (n) = 2T ( n2 ) + c
Substitute the value of T (n/2)
T (n) = 22 T ( 2n2 ) + c + 2c
Substitute the value of T (n/22 )
T (n) = 23 T ( 2n3 ) + c + 2c + 22 c
..
.
After k steps
T (n) = 2k T ( 2nk ) + c(2k − 1)
By putting n = 2k we get,
T (n) = n + (n − 1)c = Θ(n)
Tree Method
Idea : Another method where we analyse how the problem gets subdivided among subproblems and how
much cost we have paid for doing so.
Ex.1
(
2T ( n2 ) + n if n > 1
T (n) =
1 if n = 1
Lecture 3: August 7 3-3
T (n)
T (n/2) T (n/2) −−−−−−−−−−−−−−− n
T (n/4) T (n/4) T (n/4) T (n/4) − − − − − − − − − 2n/2
T (n/8) T (n/8) T (n/8) T (n/8) T (n/8) T (n/8) T (n/8) T (n/8) − − − − − − − 22 (n/4)
After k-steps, it is reduced to T (n/2k ), with cost n at each step. By putting n = 2k , we replace T (1) = 1.
As there are log n steps, and at each step, cost is n thus
T (n) = Θ(n log n)
Master Theorem
Solves special classes of the recurrence relations. The Master Theorem provides a solution to recurrence
relations of the form:
n
T (n) = aT + f (n)
b
where a ≥ 1 and b > 1 are constants, and f (n) is an asymptotically positive function. The theorem states
that:
If f (n) = O(nc ) where c < logb a, then T (n) = Θ(nlogb a ).
If f (n) = Θ(nlogb a ), then T (n) = Θ(nlogb a log n).
If f (n) = Ω(nc ) where c > logb a and af nb ≤ kf (n)(also called regularity condition) for some
k < 1 and all sufficiently large n, then T (n) = Θ(f (n)).
n
Example 1: T (n) = 2T 2 +n
Here, a = 2, b = 2, and f (n) = n.
Calculate logb a = log2 2 = 1.
Compare f (n) = n with nlogb a = n1 :
Since f (n) = Θ(nlogb a ), this falls under Case 2.
Thus, T (n) = Θ(n log n).
3-4 Lecture 3: August 7
n
Example 2: T (n) = 3T 2 +n
Here, a = 3, b = 2, and f (n) = n.
Calculate logb a = log2 3 ≈ 1.585.
Compare f (n) = n with nlogb a ≈ n1.585 :
Since f (n) = O(nc ) where c = 1 < 1.585, this falls under Case 1.
Thus, T (n) = Θ(nlog2 3 ) ≈ Θ(n1.585 ).
n
Example 3: T (n) = 2T 4 + n2
Here, a = 2, b = 4, and f (n) = n2 .
Calculate logb a = log4 2 = 0.5.
Compare f (n) = n2 with nlogb a = n0.5 :
n
Since f (n) = Ω(nc ) where c = 2 > 0.5, and we need to check the regularity condition 2f 4 ≤ kf (n).
2 2 2
2 n4 = 2 · n16 = n8 ≤ kn2 for k < 1.
Thus, T (n) = Θ(n2 ).
* Determine the scenario where the regularity condition is not met, but falls under 3rd case of the
Master theorem ??
" #
n π
Analyse the recurrence relation : T (n) = T 2 + n sin n − 2 + 2
3.1 Practice Problems
Give asymptotic upper and lower bounds for T (n) in each of the following recurrences. Assume T (n) = 1
for n ≤ 2. Make your bound as tight as possible.
T (n) = 2T (n/2) + n4
T (n) = T (7n/10) + n
T (n) = 7T (n/2) + n2
T (n) = T (n − 2) + n2
√
T (n) = 4T (n/2) + n2 n
T (n) = 2T (n/2) + n/ log n
√ √
T (n) = nT ( n) + n
