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

  • $\begingroup$ See page 68 of Property testing and parameter testing for permutations by Hoppen et al. siam.org/proceedings/soda/2010/SODA10_007_hoppenc.pdf $\endgroup$ – SandeepJ Jul 11 '10 at 18:07
  • $\begingroup$ SandeepJ, thanks. I will see if the bibliography holds some clues as well. Gerhard "Ask Me About System Design" Paseman, 2010.07.11 $\endgroup$ – Gerhard Paseman Jul 12 '10 at 4:39
  • $\begingroup$ Will, click on Users and type in "Gerhard Paseman", no double quotes. I think my total is close to 900. Part of that is due to community-wiki answers. I'll see if I can ask some really good non CW questions. Gerhard "An Account for Every Occasion" Paseman, 2010.07.11 $\endgroup$ – Gerhard Paseman Jul 12 '10 at 4:41
  • $\begingroup$ I did that, something with 200-300 points. My impression is that unregistered accounts are not name-searchable. So you may have several fragments around. The upside for MO of having them combine all your accounts into one is when somebody says "I remember Gerhard Paseman had this fascinating question/answer/comment a year ago, what was that, there was something about a unicorn and it turned out the good guy and the bad guy were twins." Then they search under your name and have a chance of finding it. $\endgroup$ – Will Jagy Jul 12 '10 at 19:02

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.