LINEAR COMPLEXITY ASSERTIONS FOR SORTING

Correctness of the execution of sorting programs can be checked by two assertions: the order assertion and the permutation assertion. The or der assertion checks if the sorted data is in ascending or descending order. The permutation assertion checks if the output data produced by sorting is a permutation of the original input data. Permutation and order assertions are sufficient for the detection of errors in the exe cution of sorting programs; however, in terms of execution time these assertions cost the same as sorting programs. An assertion. called the order-sum assertion, that has lower execution cost than sorting progr ams is derived from permutation and order assertions. The reduction in cost is achieved at the expense of incomplete checking. Some metrics are derived to quantify the effectiveness of order-sum assertion under various error models. A natural connection between the effectiveness of the order-sum assertion and the partition theory of numbers is show n. Asymptotic formulae for partition functions are derived.