Question

(Average time complexity) the Time Complexity (TC) considered is generally

referred to as the worst-case (WS) TC. Note that WS-TC reflects only the performance of an algorithm
in the worst case, as the name suggests, which does not necessarily capture its practical performance.1 In
contrast to WS-TC, another related concept, called Average Time Complexity (AV-TC), captures the average
performance of an algorithm over a large number of pre-set random instances. A typical way to evaluate
the AV-TC of a given algorithm is to first identify a class of instances and then output the average running
time over them. In the context of sorting algorithms when input size is n, we can get testing instances by
generating a given number of random permutations over [n] = {1,2,3,...,n}.
Please implement the following algorithms, namely, (1) Cocktail Sort (CS), (2) the complementary reversion
of CS (CS-R), (3) Merge Sort parameterized with an integer k = 2 (MS(k = 2)), (4) Merge Sort parameterized
with an integer k = 3 (MS(k = 3)), (5) Merge Sort parameterized with p = 2/5 (MS(p = 2/5)), (6) Quick
Sort (QS, the basic version), and (7) Randomized Quick Sort (R-QS). For each given n ∈ {102,103,104,105},
please run each algorithm ALG on K = 1000 randomly generated permutations over [n] and then output
the average as the empirical performance on an input of size n, denoted by τ(ALG,n). Please plot all values
τ(ALG,n) and see how the average running time of the seven sorting algorithms increases as the input size
n. You are encouraged to test larger values of n and K (as large as possible), as long as the total running
time is acceptable to you based on your own PCs. Note that the average running time should be measured
in milliseconds or seconds.

Answer 1

The question involves implementing several sorting algorithms and assessing their average time complexity over 1000 permutations of various input sizes, measuring this empirical performance in milliseconds or seconds.

Step-by-step explanation:

The task involves implementing and evaluating the average time complexity of different sorting algorithms. These algorithms include Cocktail Sort (CS), the complementary reversion of Cocktail Sort (CS-R), Merge Sort parameterized with integers k=2 and k=3, Merge Sort parameterized with p=2/5, Quick Sort (QS), and Randomized Quick Sort (R-QS). The evaluation requires running each algorithm on 1000 randomly generated permutations of different sizes (n) and calculating the average running time.

To approach this task, one would need to write code for each algorithm in a programming language, generate the permutations, run the algorithms, measure run time, calculate the average time τ(ALG,n) for each scenario, and finally, plot the results for analysis. Since the practical performance of an algorithm is often more relevant than the worst-case scenario, such empirical testing can reveal the efficiency of algorithms in real-world usage.