Substitution
Method Explanation
In algorithm analysis, the
substitution method is a technique used to prove the correctness and efficiency
of algorithms by recursively solving and analyzing the recurrence relations
that describe their time complexity.
In this method it involves,substituting
the solution for a problem of size n
with a function, and then using mathematical induction or other proof
techniques to verify its correctness. This method is particularly useful for
analyzing divide-and-conquer algorithms and recursive algorithms.
Substitution Method Example:-
T(n) = 2T(n/2) + n , T(1)
= 1
Solution: T(n) = 2T(n/2) + n …………....( 1 )
Substitute nàn/2
T(n/2)= 2T(n/4) + n/2 …………..(
2 )
Putting Equation (2)
in ( 1)
T(n) = 2[2T(n/4) + n/2]
+ n
= 4T(n/4) + n
+ n
=4T(n/4)+2n
-------( 3)
T(n) = 22T(n/(22))
+ 2n …………..( 4 )
Substitute nàn/4
in Equation ( 4 )
T(n/4)=2 T(n/8) = n/4 ……………(
5 )
Putting Equation ( 5 )
in Equation ( 4 )
T(n) = 4(2T(n/8) +
n/4) + 2n
= 8T(n/8) + n
+ 2n
= 23T(n/(23)
+ 3n …………..( 6 )
Substitute nà
n/8
So in Equation (6) we
can write in a general way as :-
T(n)=2 ^ i T(n/2 ^ i) +
i * n
T(1)=1 Let n/2i = 1 n = 2 i
Taking log of both the
sides.
Log2 n= i
So, the new general Equation
is :-
T(n)=n. T(1) + log2
n*n
= nT(1) + nlog2n
T(n) = n + n loqn
Therefore,the Time Complexity is ™(n.log
n)
Submitted By:
Roll No:
03
Name :
Jay Yogesh Wagh
No comments:
Post a Comment