Question

(Bubble sort complexity Question)

Here is the problem: http://f.imgtmp.com/APYz8.jpg .

For part (a), I'm really unsure as to how I should proceed.

As for (b), I need help in figuring out how the primitive operation estimations are conducted.

As for (c), I would think it is O(n^2) since the nested for loops would run n*n = n^2 times if the inner for loop did not have a -i in the "to n - 1 - i" part. So, I'm guessing it's something like O( n^2*log(n) ) but I'm just making an educated guess and have not taken any real objective steps.

Any help would be GREATLY appreciated!
Thanks

Answer 1

a) The input that would cause the worse running time would be an array that is sorted in descending order.

Reason: every loop it would have to do a swap.

b) In the worst case you would have to do

assign i = 0
arithmetic n - 1
condition i != n - 1
for (i = 0; i < n - 1; i++) {

assign j = 0
arithmetic n - 1 - i
condition j != n - 1 - i
for (j = 0; j < n - 1 - i; j++) {

arithmetic j + 1
access A[j + 1]
access A[j]
condition A[j + 1] < A[j]
if (A[j + 1] < A[j]) {
access A[j]
assign tmp = A[j]
arithmetic j + 1
access A[j + 1]
assign A[j] = A[j + 1]
assign A[j + 1] = tmp

tmp = A[j]
A[j] = A[j + 1]
A[j + 1] = tmp
}

arithmetic j++
arithmetic n - 1 - i
condition j < n - 1 - i
}

arithmetic i++
arithmetic n - 1
condition i < n - 1
}

I'm using E for the summation operator (capital sigma)

and to simplify this a little i'll assume array access starts at 1

T(n) = 3 + E(i=1 to n) (6 + (n-i+1)(13) )
T(n) = 3 + 6*n + 13*E(i=1 to n) ( (n-i+1) )

Do you know of arithmetic progressions? If not there is at least one you need to know for computer science

E(i=1 to n) (i)
1 + 2 + 3 + ... + n = n*(n+1)/2

eg 1 + 2 + 3 = 6
3*(3+1)/2 = 3*4/2 = 6

so (n-i+1)(13) will be done n times

in terms of the number of operations
E(i=1 to n) (i) = E(i=1 to n)(n-i+1)

i n-i+1
________________
1 n
2 n-1
3 n-2
. .
. .
n - 2 3
n - 1 2
n 1

See how the sum of both sides are equal

T(n) = 3 + 6*n + 13*E(i=1 to n) (i)
T(n) = 3 + 6*n + 13*n*(n+1)/2

c) big-Oh of T(n) is O(n^2)

Hope this clears up any troubles you've been having =)

Answer 2

Thanks for the detailed answer! I have a question though: is i != n - 1, for example, actually 1 primitive operation or is it 2 primitive operations since n - 1 is a primitive operation and then it's actually checking if that is not equal to i.

Answer 3

i would say two