The linear parallel-runtime conjecture for the step-wise odd-even algorithm
Statement
Consider the step-wise odd-even algorithm depicted in Figure, and let 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 , and after parallelization in . The source states that only experimental results are available beyond the general upper bound of 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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.