Design and Analysis of Algorithm
Unit 3: Divide and Conquer
algorithms
Recurrence Equation, It’s Solving
Method, & Binary Search
Compiled By
Prof. Dharmesh R. Tank
CE\IT Department, LDRP-ITR
Outline
• Introduction
• Recurrence Relations and methods to solve
recurrence
– Substitution Method,
– Recurrence Tree
– Master’s method
• Sorting (Merge Sort & Quick Sort)
• Matrix multiplication
• Binary search
The Divide-and-Conquer design
paradigm
1.Divide the problem (instance) into sub-problems.
2.Conquer the sub-problems by solving them
recursively.
3.Combine sub-problem solutions.
Divide-and-Conquer Technique
(cont.)
a problem of
size n (instance)
subproblem 1 subproblem 2
of size n/2 of size n/2
a solution to a solution to
subproblem 1 subproblem 2
A solution to It general leads to a
the original problem recursive algorithm!
Types of Algorithm
Algorithm
Iterative Recursive
A() A(n)
{ {
for(i=0;i<5;i++) if(n>0)
{ {
s=s + i; f=f * A(n/2)
} }
} }
Recurrence Equation
• Divide and conquer are recursive in nature.
• When we analyze them, we get a recurrence
relation for time complexity.
• We get running time as a function of 𝒏 (input
size) and we get the running time on inputs of
smaller sizes.
• A recurrence is a recursive description of a
function, or a description of a function in terms of
itself.
• A recurrence relation recursively defines a
sequence where the next term is a function of
the previous terms.
Methods to Solve Recurrence
• There are many methods to solve different kind
of recursive relation But we mainly focus on
three methods
Substitution Method
Recurrence Tree
Master Theorem
Substitution Method – Example 1
Time to solve the Time to solve the
instance of size n instance of size n-1
A recursive relation is generated Time Complexity:
Algorithm: T(n)= T(n-1)+1 ------------------(1)
Replace n with n-1 and n-2 in Eq (1),
A(n)
we get:
{
if(n>1) T(n-1)= T(n-2)+1 ----------------(2)
{
return A(n-1) T(n-2)= T(n-3)+1 -----------------(3)
} Substituting Eq (1), with Eq (2) & Eq (3)
} T(n)= T(n-2)+1+1
T(n)= T(n-3)+1+1+1
T(n)= T(n-3)+3 --------------(4)
𝑇 𝑛 − 1 + 1, 𝑛>1
T 𝑛 =ቊ
...
1, 𝑛=1
T(n)= T(n-k)+k ----------------(5).
---------- (6)
Substitution Method – Example 1
Our priority is to figure out basis condition that is T(1) =1 So by Eq (5)
For T(n) = k + T(n-k)
Here we need that
n-k = 1
k = n-1 Putting k’s value in Eq (5).
T(n)= (n-1)+T(n-(n-1))
T(n)= (n-1)+T(n-n+1)
T(n)= (n-1)+T(1) ‘.’ We know that T(1)=1
T(n)= (n-1)+1=n
Hence the order of growth of this algorithm
T(n)=O(n)
fall under Big O Notation.
Substitution Method – Example 2
A recursive relation is given
𝑇 𝑛 − 1 + 𝑛, 𝑛>1 ----------------(1)
T 𝑛 =ቊ
1, 𝑛=1
Replace n with n-1 and n-2 in Eq (1),
we get:
T 𝑛−1 =T 𝑛−2 +𝑛−1 ----------------(2)
T 𝑛 − 2 = T 𝑛 − 3 + 𝑛 −2 ----------------(3)
Substituting Eq (1), with Eq (2) & Eq (3)
T 𝑛 = T 𝑛 − 2 + (𝑛 − 1) + 𝑛 ---------------(4)
T 𝑛 = T 𝑛 − 3 + (𝑛 − 2) + (𝑛 − 1) + 𝑛 ---------------(5)
...
T 𝑛 = 𝑛 + (𝑛 − 1) + (𝑛 − 2) + ⋯ (𝑛 − 𝑘) + T 𝑛 − (𝑘 + 1) ----------(6)
Substitution Method – Example 2
Here we need that
Our priority is to figure out basis
𝑛 − (𝑘 + 1) = 1
condition that is T(1) =1
𝑛 − 𝑘 − 1 = 1
𝑘 = 𝑛 − 2
Hence
T 𝑛 = 𝑛 + (𝑛 − 1) + (𝑛 − 2) + ⋯ (𝑛 − 𝑛 + 2) + T 𝑛 − (𝑛 − 2 + 1)
T 𝑛 = 𝑛 + (𝑛 − 1) + (𝑛 − 2) + ⋯ (2) + T 𝑛 − 𝑛 + 1)
T 𝑛 = 𝑛 + (𝑛 − 1) + (𝑛 − 2) + ⋯ 2 + T(1)
𝑛(𝑛+1)
T 𝑛 = 𝑛 + (𝑛 − 1) + (𝑛 − 2) + ⋯ 2 + 1 We know that σ 𝑛 =
2
𝑛(𝑛+1)
T 𝑛 =
2
T 𝑛 = O(𝑛2 ) Hence the order of growth (𝑛2 ) this algorithm
fall under Big O Notation.
Substitution Method Exercises
Solve the following recursive relation using substitution method
𝑇 𝑛 − 1 + 𝑐1, 𝑜𝑡ℎ𝑒𝑟
1. T 𝑛 = ቊ
𝑐2, 𝑛=0
2.
3.
Recurrence Tree Method- Example 1
Division factor
No of divide in
Will be root
sub problem
node f(n)
2𝑇 𝑛/2 + 𝑛, 𝑛>1
T 𝑛 =ቊ
1, 𝑛=1
Step 1 0 𝑙𝑒𝑣𝑒𝑙
𝑛
𝑛 𝑛 𝑇 𝑛/2 = 2𝑇 𝑛/4 + 𝑛/2
𝑇( ) 𝑇( )
2 2
Recurrence Tree Method- Example1
Step 2
0 𝑙𝑒𝑣𝑒𝑙
𝑛
1 𝑙𝑒𝑣𝑒𝑙
𝑛/2 𝑛/2
𝑇 𝑛/22 = 2𝑇 𝑛/23 + 𝑛/22
𝑛 𝑛 𝑛 𝑛
𝑇( 2 ) 𝑇( 2 ) 𝑇( 2 ) 𝑇( 2 )
2 2 2 2
Recurrence Tree Method- Example 1
Step 3 𝑻𝒐𝒕𝒂𝒍 𝑾𝒐𝒓𝒌
0 𝑙𝑒𝑣𝑒𝑙 𝑛
𝑛 𝑡𝑖𝑚𝑒𝑠
20
1 𝑙𝑒𝑣𝑒𝑙 𝑛 𝑛
21 21
𝑛 𝑡𝑖𝑚𝑒𝑠
2 𝑙𝑒𝑣𝑒𝑙 𝑛 𝑛 𝑛 𝑛
22 22 22 22
𝑛 𝑡𝑖𝑚𝑒𝑠
…
…
…
…
𝑛 𝑛 𝑛 𝑛 𝑛 𝑛
𝑇( 𝐾 ) 𝑇( 𝐾 ) 𝑇( 𝐾
) 𝑇( 𝐾 ) … 𝑇( 𝐾 )
2
𝑇( 𝐾 ) 𝑛 𝑡𝑖𝑚𝑒𝑠
2 2 2 2 2
𝑘 𝑙𝑒𝑣𝑒𝑙
𝑛 𝑛 𝑛 𝑛
……
2𝐾+1 2𝐾+1 2𝐾+1 2𝐾+1
Recurrence Tree Method- Example 1
Step 4
0 𝑙𝑒𝑣𝑒𝑙 𝑛
𝑛 𝑡𝑖𝑚𝑒𝑠
20
1 𝑙𝑒𝑣𝑒𝑙 𝑛 𝑛
𝑛 𝑡𝑖𝑚𝑒𝑠
21 21
2 𝑙𝑒𝑣𝑒𝑙 𝑛 𝑛 𝑛 𝑛
𝑛 𝑡𝑖𝑚𝑒𝑠
22 22 22 22
…
…
…
…
…
…
𝑛 𝑛 𝑛 𝑛 𝑛 𝑛
…
2𝐾 2𝐾 2𝐾 2𝐾 2𝐾 2𝐾
𝑘 𝑙𝑒𝑣𝑒𝑙𝑠 𝑇(1) 𝑇(1) 𝑇(1) 𝑇(1) … 𝑇(1) 𝑛 𝑡𝑖𝑚𝑒𝑠
Recurrence Tree Method- Example 1
Step 5 Here our target to satisfy the condition 𝑇 1 = 1
𝑛
⇒ 𝑘=1
2
⇒ 𝑛 = 2𝑘
⇒ 𝑘 = log 𝑛
Here tree level are 0,1,2,3…..k levels. So total no of recurrence will be k+1.
Hence time taken by each recurrence function will be k+1= log 𝑛 + 1
So Time complexity of the given recurrence function
= n* Time taken by recurrence function
𝑇 𝑛 = 𝑛 ∗ (log 𝑛 + 1)
𝑇 𝑛 = 𝑛 ∗ log 𝑛 + 𝑛
𝑇 𝑛 ≤ 𝑛 log 𝑛
𝑻 𝒏 = 𝑶(𝒏 𝒍𝒐𝒈 𝒏)
Recurrence Tree Method- Example 2
2𝑇 𝑛/2 + 𝑐, 𝑛>1
T 𝑛 =ቊ
𝑐, 𝑛=1
𝑻𝒐𝒕𝒂𝒍 𝑾𝒐𝒓𝒌
Step 1
0 𝑙𝑒𝑣𝑒𝑙 𝑇 𝑛 = 𝑐 𝐶
1 𝑙𝑒𝑣𝑒𝑙 𝑐 + 𝑐 = 2𝑐
𝑇(𝑛/2) 𝑇(𝑛/2)
Recurrence Tree Method- Example 2
Step 2
𝑻𝒐𝒕𝒂𝒍 𝑾𝒐𝒓𝒌
0 𝑙𝑒𝑣𝑒𝑙 𝑇 𝑛 = 𝑐 𝐶
1 𝑙𝑒𝑣𝑒𝑙 𝑐 + 𝑐 = 2𝑐
𝑐 𝑐
Recurrence Tree Method- Example 2
Step 3
𝑻𝒐𝒕𝒂𝒍 𝑾𝒐𝒓𝒌
𝑇 𝑛 =
0 𝑙𝑒𝑣𝑒𝑙 𝑐 𝐶
1 𝑙𝑒𝑣𝑒𝑙 𝑐 + 𝑐 = 2𝑐
𝑐 𝑐
𝑐 + 𝑐 + 𝑐 + 𝑐 = 4𝑐
2 𝑙𝑒𝑣𝑒𝑙 𝑇(𝑛/22 ) 𝑇(𝑛/22 ) 𝑇(𝑛/22 ) 𝑇(𝑛/22 )
Recurrence Tree Method- Example 2
Step 4
𝑻𝒐𝒕𝒂𝒍 𝑾𝒐𝒓𝒌
𝑇 𝑛 =
0 𝑙𝑒𝑣𝑒𝑙 𝑐 𝐶
1 𝑙𝑒𝑣𝑒𝑙 𝑐 + 𝑐 = 2𝑐
𝑐 𝑐
𝑐 + 𝑐 + 𝑐 + 𝑐 = 4𝑐
2 𝑙𝑒𝑣𝑒𝑙 𝑐 𝑐 𝑐 𝑐
…
…
𝑛 𝑛 𝑛
𝑘 𝑙𝑒𝑣𝑒𝑙 𝑇( 𝐾 ) 𝑇( 𝐾 ) … 𝑇( 𝐾 )
2 2 2 𝑛 𝑡𝑖𝑚𝑒𝑠
Recurrence Tree Method- Example 2
Step 4
𝑻𝒐𝒕𝒂𝒍 𝑾𝒐𝒓𝒌
𝑇 𝑛 =
0 𝑙𝑒𝑣𝑒𝑙 𝑐 𝐶
1 𝑙𝑒𝑣𝑒𝑙 𝑐 + 𝑐 = 2𝑐
𝑐 𝑐
𝑐 𝑐 + 𝑐 + 𝑐 + 𝑐 = 4𝑐
2 𝑙𝑒𝑣𝑒𝑙 𝑐 𝑐 𝑐
…
…
𝑛 𝑛 𝑛
𝑘 𝑙𝑒𝑣𝑒𝑙 𝑇( 𝐾 ) 𝑇( 𝐾 ) … 𝑇( 𝐾 )
2 2 2
𝑇(1) 𝑇(1) … 𝑇(1) 𝑛𝑐 𝑡𝑖𝑚𝑒𝑠
Recurrence Tree Method- Example 2
Step 5 Here our target to satisfy the condition 𝑇 1 = 1
𝑛
⇒ 𝑘=1
2
⇒ 𝑛 = 2𝑘
⇒ 𝑘 = log 𝑛
Here tree level are 0,1,2,3…..k levels. So total no of recurrence will be k+1.
And total work doneT(n) = 𝑐 + 2𝑐 + 4𝑐 + 8𝑐 … … + 𝑛𝑐
= 𝑐 + 2𝑐 + 4𝑐 + 8𝑐 … … + 2𝑘 𝑐
= 𝑐(1 + 2 + 4 + 8 … … + 2𝑘 ) We know that
= 𝑐 20 + 21 + 22 + 23 … … + 2𝑘
𝑘+1 − 1 𝑟 𝑘+1 − 1
2 𝑟𝑘 =
= c 2𝑘 = 𝑐 ∗ 𝑟−1
2−1
= 𝑐 ∗ 2𝑘+1 − 1
⇒ 𝑇(𝑛) = 𝑐(2𝑛 − 1) ⇒ 𝑇(𝑛) = 𝑂(𝑛)
Recurrence Tree Method- Example 3
Solve T(n) = T(n/4) + T(n/2) + n2:
Recurrence Tree Method- Example 3
Solve T(n) = T(n/4) + T(n/2) + n2:
T(n)
Solve T(n) = T(n/4) + T(n/2) + n2:
n2
T(n/4) T(n/2)
Solve T(n) = T(n/4) + T(n/2) + n2:
n2
(n/4)2 (n/2)2
T(n/16) T(n/8) T(n/8) T(n/4)
Solve T(n) = T(n/4) + T(n/2) + n2:
n2
(n/4)2 (n/2)2
(n/16)2 (n/8)2 (n/8)2 (n/4)2
Q(1)
Solve T(n) = T(n/4) + T(n/2) + n2:
n2 𝑛2
(n/4)2 (n/2)2
(n/16)2 (n/8)2 (n/8)2 (n/4)2
Q(1)
Solve T(n) = T(n/4) + T(n/2) + n2:
n2 𝑛2
(n/4)2 (n/2)2 5 2
𝑛
16
(n/16)2 (n/8)2 (n/8)2 (n/4)2
Q(1)
Solve T(n) = T(n/4) + T(n/2) + n2:
n2 𝑛2
(n/4)2 (n/2)2 5 2
𝑛
16
(n/16)2 (n/8)2 (n/8)2 (n/4)2 25 2
𝑛
256
…
Q(1)
Solve T(n) = T(n/4) + T(n/2) + n2:
n2 𝑛2
(n/4)2 (n/2)2 5 2
𝑛
16
(n/16)2 (n/8)2 (n/8)2 (n/4)2 25 2
𝑛
256
…
Q(1)
Total = ( 2
( ) ( )
n 1 + 16 + 16 + 16 +
2 5 5 5 3
)
= Q(n2) geometric series
Recurrence Tree Exercises
Solve the following recursive relation using Recurrence Tree method
2𝑇 𝑛/2 + 1, 𝑛>1
1 T 𝑛 =ቊ
1, 𝑛=1
3𝑇 𝑛/4 + 𝑐𝑛2 𝑛 > 1
2 T 𝑛 =ቊ
𝑐, 𝑛=1
2𝑇 𝑛/2 + 𝑐𝑛, 𝑛>1
3 T 𝑛 =ቊ
𝑐, 𝑛=1
Master Theorem
f(n)
Case 1: 𝑖𝑓 log 𝑏 𝑎 > 𝑘 𝑡ℎ𝑒𝑛 θ(𝑛log𝑏 𝑎 )
Case 2: 𝑖𝑓 log 𝑏 𝑎 = 𝑘 𝑡ℎ𝑒𝑛
Here we need
(a) If P > − 1 then θ(𝑛𝑘 log 𝑛 𝑝+1
)
to find out
(b) If P = − 1 then θ(𝑛𝑘 log log 𝑛) 𝒍𝒐𝒈𝒃 𝒂 , 𝒑 & 𝒌
value
(c) If P < − 1 then θ(𝑛𝑘 )
Case 3:
𝑖𝑓 log 𝑏 𝑎 < 𝑘 𝑡ℎ𝑒𝑛
(a) If P ≥ 0 then θ (𝑛𝑘 log 𝑛 𝑝 )
(b) If P < 0 then O (𝑛𝑘 )
Master Theorem Example 1
𝑛
T 𝑛 = 2𝑇 +1
2
Solution: 𝑎 = 2, 𝑏 = 2, 𝑓 𝑛 = 𝑛0 (𝑙𝑜𝑔0 𝑛) = 1 , 𝑆𝑜 𝑝 = 0 & 𝑘 = 0
Here ⇒ log 𝑏 𝑎 > k
⇒ log 2 2 > 0
⇒1>0
So Case 1 satisfied 𝑖𝑓 log 𝑏 𝑎 > 𝑘 𝑡ℎ𝑒𝑛 θ(𝑛log𝑏 𝑎 )
⇒ T 𝑛 =θ(𝑛log2 2 ) 𝑏𝑒𝑐𝑎𝑢𝑠𝑒 log 2 2 = 1
⇒ T 𝑛 = θ(𝑛)
Master Theorem Example 2
𝑛
T 𝑛 = 2𝑇 +𝑛
2
Solution: 𝑎 = 2, 𝑏 = 2, 𝑓 𝑛 = 𝑛1 (𝑙𝑜𝑔0 𝑛) = 𝑛 , 𝑆𝑜 𝑝 = 0 & 𝑘 = 1
Here ⇒ log 𝑏 𝑎 = k
⇒ log 2 2 =1
⇒1=1
So Case 2(a) satisfied 𝑖𝑓 log 𝑎 = 𝑘 𝑡ℎ𝑒𝑛
𝑏
with p=0 condition
(a) If P > − 1 then θ(𝑛𝑘 log 𝑛 𝑝+1
)
⇒ T 𝑛 =θ(𝑛1 log 𝑛 0+1
)
⇒ T 𝑛 = θ(𝑛 log 𝑛 )
Master Theorem Example 3
𝑛
T 𝑛 = 2𝑇 + 𝑛0.51
4
Solution:
𝑎 = 2, 𝑏 = 4, 𝑓 𝑛 = 𝑛0.51 (𝑙𝑜𝑔0 𝑛) = 𝑛0.51 , 𝑆𝑜 𝑝 = 0 & 𝑘 = 0.51
Here ⇒ log 𝑏 𝑎 = k
⇒ log 4 2 = 0.51
⇒ 0.5 < 0.51
So Case 3(a) satisfied 𝑖𝑓 log 𝑏 𝑎 < 𝑘 𝑡ℎ𝑒𝑛
with p=0 condition
(a) If P ≥ 0 then θ (𝑛𝑘 log 𝑛 𝑝 )
⇒ T 𝑛 =θ(𝑛0.51 log 𝑛 0 )
⇒ T 𝑛 = θ(𝑛0.51 )
Master Theorem Exercises
Solve the following recursive relation using Master Theorem method
𝑛
1. T 𝑛 = 8𝑇
𝑛
+𝑛 8. T 𝑛 = 2𝑇 + 𝑛(log 𝑛)−2
2 2
𝑛 𝑛
2. T 𝑛 = 9𝑇 +1 9. T 𝑛 = 𝑇 + 𝑛2
3 2
𝑛 𝑛
3. T 𝑛 = 9𝑇 +𝑛 10. T 𝑛 = 𝑇 + 𝑛2 log 𝑛
3 2
𝑛 𝑛 1
4. T 𝑛 = 4𝑇 + 𝑛2 11. T 𝑛 = 0.5𝑇
2
+
𝑛
2
𝑛 𝑛
5. T 𝑛 = 4𝑇 + 𝑛2 log 𝑛 12. T 𝑛 = 3𝑇 + 𝑛2
2 4
𝑛 2𝑛
6. T 𝑛 = 8𝑇 + 𝑛3 13. T 𝑛 = 𝑇
3
+1
2
𝑛 𝑛
7. T 𝑛 = 2𝑇 +
2 log 𝑛
Binary Search
• Binary Search is an extremely well known
instance of divide and conquer approach.
• Let A[1,2,…..n] be array of increasing sorted
order, that is A[i]<=A[j] whenever 1<=i<=j<=n
• Let x is some number. The problem consists of
finding x in the array A if it is there.
Binary Search Example
• Input: Sorted array of integer values.
• Search value X=7
Data 3 7 8 14 46 57 71 85 90
Index 0 1 2 3 4 5 6 7 8
Step 1: Find the mid point of the sorted array using
its index value
𝐻𝑖𝑔ℎ 𝐼𝑛𝑑𝑒𝑥 + 𝐿𝑜𝑤 𝐼𝑛𝑑𝑒𝑥 8
𝑀𝑖𝑑 𝑣𝑎𝑙𝑢𝑒 = = =4
2 2
Data 3 7 8 14 46 57 71 85 90
Index 0 1 2 3 4 5 6 7 8
Binary Search Example
Step 2: Check whether the mid position number is
equal to the search value (x=7)
Data 3 7 8 14 46 57 71 85 90
Index 0 1 2 3 4 5 6 7 8
𝐼𝑠 𝑥 = 7 𝑖𝑠 𝑚𝑖𝑑 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 𝑛𝑢𝑚𝑏𝑒𝑟?
Step 3: If not then divide the list into two part:
Before Mid Point and After Mid Point
Data 3 7 8 14 46 57 71 85 90
Index 0 1 2 3 4 5 6 7 8
𝑆𝑒𝑎𝑟𝑐ℎ 𝑓𝑜𝑟 𝑡ℎ𝑒 𝑡𝑎𝑟𝑔𝑒𝑡 𝑖𝑛 𝑡ℎ𝑒 𝑎𝑟𝑒𝑎 𝑎𝑠
𝑆𝑒𝑎𝑟𝑐ℎ 𝑣𝑎𝑙𝑢𝑒 = 7 < 𝑚𝑖𝑑𝑝𝑜𝑖𝑛𝑡 𝑜𝑟 𝑆𝑒𝑎𝑟𝑐ℎ 𝑣𝑎𝑙𝑢𝑒 = 7 > 𝑚𝑖𝑑𝑝𝑜𝑖𝑛𝑡
Binary Search Example
Step 4: Find the approximate midpoint which is
equal to the search value (x=7)
Data 3 7 8 14 46 57 71 85 90
Index 0 1 2 3 4 5 6 7 8
𝐼𝑠 𝑥 = 7 𝑖𝑠 𝑚𝑖𝑑 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 𝑛𝑢𝑚𝑏𝑒𝑟?
Step 5: If the mid point value is equal to the search
value then successful else further divide the list.
Data 3 7 8 14 46 57 71 85 90
Index 0 1 2 3 4 5 6 7 8
𝑇ℎ𝑒 1 𝑖𝑠 𝑡ℎ𝑒 𝑖𝑛𝑑𝑒𝑥 𝑣𝑎𝑙𝑢𝑒 𝑜𝑓 𝑡ℎ𝑒 𝑠𝑒𝑎𝑟𝑐ℎ 𝑣𝑎𝑙𝑢𝑒 𝑥 = 7.
Iteration Algorithm of Binary Search
Recursive Algorithm of Binary Search
Function binsearch(T[1,…,n], x) 𝑻𝒐𝒕𝒂𝒍 𝑾𝒐𝒓𝒌
if n = 0 or x > T[n] then
𝑻 𝟏 =𝟏
return n + 1
else
return binrec(T[1,…,n], x)
Function binrec(T[i,…,j], x)
if i = j then
return i
k ← (i + j) ÷ 2
if x ≤ T[k] then
return binrec(T[i,…,k],x)
else 𝑻 𝒏/𝟐
return binrec(T[k + 1,…,j], x)
Analysis of Binary Search
• Worst case: key is not found in the array
• Each time through the loop, at least half of the
remaining locations are rejected:
• After first time through, <= n/2 <= n/21 remain
• After second time through, <= n/4 <= n/22 remain
• After third time through, <= n/8 <= n/23 remain
• After kth time through, <= n/2𝑘 remain
Analysis of Binary Search
1. Worst Case:
By Using Master Theorem Method
1𝑇 𝑛/2 + 1, 𝑛>1
T 𝑛 =ቊ
1, 𝑛=1
𝑎 = 1, 𝑏 = 2, 𝑓 𝑛 = 𝑛0 (𝑙𝑜𝑔0 𝑛) = 1 , 𝑆𝑜 𝑝 = 0 & 𝑘 = 0
Here ⇒ log 𝑏 𝑎 = k
⇒ log 2 1 =0
⇒0=0
So Case 2(a) satisfied 𝑖𝑓 log 𝑏 𝑎 = 𝑘 𝑡ℎ𝑒𝑛
with p=0 condition
(a) If P > − 1 then θ(𝑛𝑘 log 𝑛 𝑝+1 )
⇒ T 𝑛 =θ(𝑛0 log 𝑛 0+1
)
⇒ T 𝑛 = θ log 𝑛
Analysis of Binary Search
1. Worst Case:
By Using Substitution Method
𝑛
T 𝑛 = 1𝑇 +1 … … . 𝐸𝑞𝑛 1
2
𝑛
T 𝑛/2 = 1𝑇 +1 … … . 𝐸𝑞𝑛 2
4
𝑛
T 𝑛/4 = 1𝑇 +1 … … . 𝐸𝑞𝑛 3
8
𝑅𝑒𝑝𝑙𝑎𝑐𝑒 𝑡ℎ𝑒 𝑒𝑞𝑢 1 𝑤𝑖𝑡ℎ 𝑡ℎ𝑒 𝑒𝑞𝑢 2 & 3
𝑛 𝑛
T 𝑛 =𝑇 +1+1=𝑇 2 +2
4 2
𝑛 𝑛
T 𝑛 =𝑇 +1+1+1=𝑇 3 +3
8 2
……
𝑛
T 𝑛 = 𝑇 𝑘 + 1 + 2 + 3………+ 𝑘
2
Analysis of Binary Search
Here our target to satisfy the condition 𝑇 1 = 1
𝑛
⇒ 𝑘=1
2
⇒ 𝑛 = 2𝑘
⇒ 𝑘 = log 𝑛
T 𝑛 = 𝑇 1 + 𝑘 𝑡𝑖𝑚𝑒𝑠
‘.’ 𝑘 = log 𝑛
T 𝑛 = 1 + log 𝑛
⇒ T 𝑛 = θ log 𝑛
Analysis of Binary Search
1. Worst Case:
T 𝑛 = θ (log 𝑛) 𝑜𝑟 𝑂 (log 𝑛)
Hence the order of growth in worst case for
binary search θ (log 𝑛) or O (log 𝑛)
2. Best Case: In this condition it will not gone in recursive loop.
So At that time only one element in the list.
T 𝑛 = θ(1)
3. Average Case:
T 𝑛 = θ (log 𝑛) 𝑜𝑟 𝑂 (log 𝑛)
