A Statistical Analysis of Bubble Sort in terms of Serial and Parallel Computation

摘要

In some recent papers, the weight based statistical bounds haveudarguably explained time complexity better than the count basedudmathematical bounds. This is definitely true for average caseudwhere for an arbitrary code it is difficult to identify the pivotaludoperation or pivotal region in the code for taking the expectationudand/or when the probability distribution, over which expectationudis taken, becomes unrealistic over the problem domain. In worstudcase, it can certify whether a mathematical bound is conservativeudor not. Here we revisit the results on Bubble sort in sequentialudmode and make an independent study of the same algorithm inudparallel mode using statistical bound