this is my recursive code how to analyse it time complexity how to find it for recursive function
Duplicate character format
@shampblocks
hello shubham,
a)one way is to use master theorem.
b) second is to build recurrence tree .
for the current solution
recursion will be
t(n)=t(n-1) + O(1) (time taken to perfom this step i.e from n to n-1 )
t(n-1)=t(n-2) + O(1)
t(n-2)=t(n-3)+O(1)
…
…
,…
t(2)=t(1) + O(1)
t(1)=… O(1) //base case
add all equation
we will get
t(n)= n*O(1)
which means O(n) will be this function time complexity.
similary u can find others time complexity
t(n)=t(n/2) + O(1) … … … … … … … . // binary search on solving u will get O(logn)
t(n)=2t(n/2) + O(n)<- to merge … . . . . . .// mergesort O(nlogn)
for merge sort how to solve mathematically ?? as above can you explain
@shampblocks
it is simple
lets do it together.
T(n) =T(n/2)
total how may steps above recurrence will take to become T(1)
it depends on n value i think for smaaller case i can guess logn like for 4== log(2)
2 step
t(4)=t(2) 1st step
t(2)=t(1) 2nd step
is this correct??
yeah correct .basically log2(n) steps will be there
but that n is also coming on other recursive calls
and why we are stoping at T(1)?? i think it will be the case when base case is at n==1?? correct me if i am wrong
yeah n=1 is base case
@shampblocks
T(n)=2T(n/2) + O(n)
T(n/2)=2T(n/4)+O(n/2)
T(n/4)=2T(n/8)+O(n/4)
T(n/8=2*T(n/16)+O(n/8)
…
…
…
T(2)=2T(1)+O(2)
T(1)=O(1)
now multiply first equltion with 1 ,second with 2 ,third with 2^2,fourth with 2^3… so on and add.
u will get
T(n) =O(n) + O(n) + O(n) … <- total logn such terms will be there
T(n)=log(n)*n
now i got it thanks sir…
and one more question we are approximating 2*O(n/2) with O(n)??
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.