sorting we prove the lower bound first by constructing bad case firstwe choose to be power of this makes all the increments evenexcept for the last incrementwhich is nowwe will give as input an array with the / largest numbers in the even positions and the / smallest numbers in the odd positions (for this proofthe first position is position as all the increments except the last are evenwhen we come to the last passthe / largest numbers are still all in even positions and the / smallest numbers are still all in odd positions the ith smallest number ( < / is thus in position before the beginning of the last pass restoring the ith element to its correct place requires moving it - spaces in the array thusto merely place the  / / smallest elements in the correct place requires at least = ( work as an examplefigure shows bad (but not the worstinput when the number of inversions remaining after the -sort is exactly + + + + + + thusthe last pass will take considerable time to finish the proofwe show the upper bound of ( as we have observed beforea pass with increment hk consists of hk insertion sorts of about /hk elements since insertion sort is quadraticthe total cost of pass is (hk ( /hk = ( /hk summing over all passes gives total bound of oti= /hi ( ti= /hi because the increments form geometric series with common ratio and the largest term in the series is ti= /hi thus we obtain total bound of ( the problem with shell' increments is that pairs of increments are not necessarily relatively primeand thus the smaller increment can have little effect hibbard suggested slightly different increment sequencewhich gives better results in practice (and theoreticallyhis increments are of the form although these increments are almost identicalthe key difference is that consecutive increments have no common factors we now analyze the worst-case running time of shellsort for this increment sequence the proof is rather complicated theorem the worst-case running time of shellsort using hibbard' increments is ( / proof we will prove only the upper bound and leave the proof of the lower bound as an exercise the proof requires some well-known results from additive number theory references to these results are provided at the end of the for the upper boundas beforewe bound the running time of each pass and sum over all passes for increments hk / we will use the bound ( /hk from the start after -sort after -sort after -sort after -sort figure bad case for shellsort with shell' increments (positions are numbered to