ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Consider the step-wise odd-even algorithm depicted in Figure, and let NN denote the number of elements being sorted. Its sequential worst-case runtime is compared with Bubble Sort, while parallelization executes the applicable row and column operations simultaneously. Linear parallel-runtime conjecture. The step-wise odd-even algorithm depicted in Figure runs like Bubble Sort in worst-case time O(N2)\mathcal{O}(N^2), and after parallelization in O(N)\mathcal{O}(N). The source states that only experimental results are available beyond the general upper bound of O(N!)\mathcal{O}(N!) and presents this conjecture as motivated by first experiments and intuition; its status is unresolved.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.