8 problems

Let $I(n,p)$ be the number of inversions produced by unreliable Quicksort on $n$ items when each comparison is erroneous with probability $p$. Assume that $(np)^{-1}\sim\log n$, an…

Let $I(n,p)$ be the number of inversions produced by unreliable Quicksort on $n$ items when each comparison is erroneous with probability $p$, and let $U$ denote the random variabl…

Let $Y_n$ be the normalized number of comparisons used by Quicksort on $n$ items, and let $Y$ be its limiting random variable. Write $d_{\text{KS}}$ for the Kolmogorov–Smirnov dist…

Let $K\in\mathbb{N}$ and let $Z_K$ be the centered, square-integrable limiting random variable characterized by … where $D,Z_K^{(0)},\ldots,Z_K^{(K)}$ are independent and each…

For $K\text{-pivot}$ QuickSort, let $X_n$ be the number of key comparisons, and let … be the more precise expansion established in the paper for $K\leq 4$. Full-expansion conjectur…

Let $F$ be the limiting QuickSort distribution function, let $\overline F(x)=1-F(x)$, and for $x\geq 2e$ let $w=w(x)\geq 1$ be the unique real solution of … Also define … The exact…

Consider a Quicksort algorithm that chooses the pivot at each step as the median of a random subsample of size $k=k(n)\sim c n^\alpha$, where $n$ is the size of the list being spli…

Let Yaroslavskiy's algorithm and classic Quicksort be implementations of Quicksort, and consider computational models that assign constant cost contributions to individual instruct…