Question 1: Let's say we have bubble sort algorithm which sorts numbers in ascending order. Intuitively one might agree that the worst case input for this algorithm is array already sorted in descending order. Like I said intuitively one might agree, but I am looking for a proof or formal argument why in such case, array already sorder in descending order is the worst case (and why not other arrangement of elements is worse than that worse case).
Also, aside, if you can comment on my below proof which computes worst case complexity of bubble sort WITHOUT the question 1, I would also appreciate.
In other words i would appreciate: (a) answer on question1, and (b) if my proof below (which doesn't rely on question 1) is correct.
PROOF(might not be written down in best way but hope you get the idea):
A[i] be element in array, such that it is
x[j]-th biggest where
(e.g. , in array [10,1,22,3,4] 10 is 4th biggest, where
x = [0,1,2,3,4]).
By definition in bubble sort, if I compare ALL elements with
it will lose at most
x[j]-1 times (e.g. 10 will lose with with 1,3,4 because it was 4th biggest) with other elements - or in other words I will need
It follows that for each A[i] it can be swapped at most x[j] times.
0+1+2+..+j = j*(j+1)/2.