algorithm - Time Complexity of Insertion and Selection sort When there are only two key values in an array -

i reviewing algorithm, 4th editon sedgewick recently, , come across such problem , cannot solve it.

the problem goes this:

2.1.28 equal keys. formulate , validate hypotheses running time of insertion sort , selection sort arrays contain 2 key values, assuming values equally occur.

explanation: have n elements, each can 0 or 1 (without loss of generality), , each element x: p(x=0)=p(x=1).

any welcomed.

selection sort:

the time complexity going remain same (as without 2 keys assumption), independent on values of arrays, number of elements.
time complexity selection sort in case o(n^2)

however, true original algorithm scans entire tail of array each outer loop iteration. if optimize find next "0", @ iteration i, since have "cleared" first i-1 zeros, i'th 0 mean location @ index 2i. means each time, inner loop need 2i-(i-1)=i+1 iterations.
suming be:

1 + 2 + ... + n = n(n+1)/2 

which is, unfortunately, still in o(n^2).

another optimization "remmber" have last stopped. improve complexity o(n), since don't need traverse same element more once - that's going different algorithm, not selection sort.

insertion sort:

here, things more complicated. note in inner loop (taken wikipedia), number of operations depends on values:

while j > 0 , a[j-1] > x 

however, recall in insertion sort, after ith step, first i elements sorted. since assuming p(x=0)=p(x=1), average of i/2 elements 0's , i/2 1's.
this means, time complexity on average, inner loop o(i/2).

summing you:

1/2 + 2/2 + 3/2 + ... + n/2 = 1/2* (1+2+...+n) = 1/2*n(n+1)/2 = n(n+1)/4 

the above however, still in o(n^2).

---

the above not formal proof, because implicitly uses e(f(e(x)) = e(f(x)), not true, can give guidelines how formally build proof.