recurrence relation
Recurrence equation
hello @Vikaspal
no the recurrence relation is not correct.
how can we say that there will always be n/2 elements in subtree.
correct recurrence relation will be
t(n)=1+t(m) + t(n-m-1) where m is number of nodes in one subtree .
yeah ,
see total n nodes are there ,
1 is for root node , m is number of nodes in one subtree.
then how many nodes we are left with ,it will be n-m-1.
this will be count of nodes in another subtree so we can write
t(n)=1 + t(m)+ t(n-m-1)
to get worst case complexity simply put m =0 .
and then we will get
t(n)=1+t(0)+t(n-1)
which is
t(n)=1+t(n-1)
on solving we will get O(n) as its worst case complexity
@aman212yadav okay i got somepoint actually . Can u give some resources where i calculate recurrence relation question for tree.
I m solution this way but now i m really confused
for the binary tree…
check gfg… . … …
also learn about masters theorem
@aman212yadav
Can u tell me where i m wrong when calculating the recurrence relation if i m able to derive the correct recurrence relation than it be easier for me aply master method.
In recursion we divide the problem in some problem and then found out the complexity but for tree is different…
the recurrene relation u derived was not correct that why u were getting wrong complexity.
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.