Doubt in the complexity

#1

Sir, when we calculate the time complexity of bubble sort using the other method of loops ,it comes to be k(n)(n-1)/2 , but when I solve it using recurrence method, it comes to be k(N)(N+1)/2… Can you explain me why it is coming different?

#2

hello @vageesha

this is recurrence relation for bubble sort->

T(n)=T(n−1)+(n−1)
if u solve this u will get
k (n(n-1)/2) only.

btw in time complexity analysis we treat both the expression as O(N^2), so It doesnt matter much whether it is N*(N+1)/2 OR N*(N-1)/2

#3

Sir, in the video T(n) was written to be equal to t(n-1)+(n) which confused me.

#4

that is also correct depends how u are implementing bubble sort.

the best way to represent recurrence
is
T(n)=T(n-1) + O(N) // O(N) represents that we are doing some linear task

#5

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.