how to derive recurrence relation for the bubblesort implemented in the video recursively and without loop?
doesn’t the implementation with no loop falls into infinite loop when given an empty array?
Bubblesort issue
hello reechika,
recurrence relation will be
T(n) = T(n-1) + n // O(n) is to push maximum element to the last index by swapping and T(n-1) is time to sort remaining element.
T(n)=T(n-1)+n
T(n-1)=T(n-2)+n-1
T(n-2)=T(n-3)+n-2
T(n-3)=T(n-4)+n-2
…
…
…
T(1)=1 //base case
T(0)=0 // base base
add all equations
T(n)=n + n-1 + n-2 + n-3 + n-4 + … … + 1+ 0
T(n)=n*(n+1)/2
T(n) =o(n^2)
to handle empty array u can add one more base case i.e if n=0 then return;
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.