2 problems

Critical-region conjecture. The critical regions are characterized by the equation

Consider the step-wise odd-even algorithm depicted in Figure, and let $N$ denote the number of elements being sorted. Its sequential worst-case runtime is compared with Bubble Sort…