Let $n > 1$ be an integer. Let $A$ be an array, indexed from $1$ to $n$, of $n$ values $A(i)$ coming from the finite set $\{0,1\}$. (More generally, the values can come from any totally ordered set, but I only need a two element set for now.)

Let us count the number of inversions in A, that is the number of pairs $(i,j)$ with $i < j$ and $A(i) > A(j)$. Using $[\quad ]$ for Iverson notation, this is

$$I = \sum_{ 1 \le i \le j \le n } [A(i) > A(j)]$$

I call the quantity $I/n^2$ the inversion density of $A$. As an exercise you can show the inversion density falls in the closed interval $[0, 1/4]$.

Question: Is this (inversion density) or a closely related concept present in the literature? If so, please tell me where.

I am still wading through the sorting literature, where number of inversions in an array are considered, but I have yet to see anything regarding a density. I have not yet found a successful online search; if a good search term is proffered I will try it as a substitute for a good reference.

Motivation: I did some research on Combsort and was looking for worst case complexity results. After finding some bad (good) cases, I saw that the same ideas had been more fully developed in the two papers listed below. In particular Poonen has a proposition which can be phrased in terms of inversion density as: there is an absolute constant $c$ so that, for any length $n$, $0$-$1$ array $A$ and for any integer $j$ with $1 < j \le n,$ there is a contiguous length $j$ subarray $B$ (so $B(k) = A(l+k-1)$ for some $l$ and $1 \le k \le j$ ) such that the inversion density of $B$ is at least $c$ times the inversion density of $A$.

Poonen shows $c \ge 1/256$. I can tighten his argument to show $c \ge 1/32$, and suspect $c = 1/2$. I also suspect the proposition holds for arrays with values from any totally ordered set.

References (Please add to this!):

Mark Allen Weiss and Robert Sedgewick, "Tight Lower Bounds for Shellsort", Journal of Algorithms Volume 11, Issue 2, June 1990, Pages 242-251

B. Poonen, “The worst case in Shellsort and related algorithms,” J. of Algorithms 15, 1993, 101-124.

Gerhard "Ask Me About System Design" Paseman, 2010.07.10


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.