CODEWITHSUNDEEP
algorithm
Little
Little

Reputation: 3477

bubble sort complexity analysis

Maybe this question has been asked a bunch of times, but I have a doubt. In the following algorithm:

BubbleSort(v[n])
i←0
exchange←V
while (exchange)
    exchange←F
    i←i+1
    for pos=0 to n-i
        if v[pos]>v[pos+1] then
            swap(v[pos],v[pos+1])
            exchange←V
        endif
    endfor
endwhile

I have analyzed it like this:

enter image description here

but I have a doubt if I have done the right thing, because if I analyze the inner loop I can say that I have:

enter image description here

where I can say that c depends on the value of the outer while loop, because it could be active or not, which analysis is more accurate of the both that I have outlined here?

Thanks

Upvotes: 0

Views: 90

Answers (1)

user2357112
user2357112

Reputation: 282026

Both of your analyses are wrong.

In your first analysis, when you eliminate the outer sum, you treat the expression inside the sum as if it's independent of the summation variable when it's not. Your work after that has an i in it even after the sum that defines i is eliminated, a clear sign that you've done something wrong.

In your second analysis, you forget about c after the ....

Upvotes: 1

Related Questions