Finding number of smaller elements for each element in an array efficiently
The naive algorithm for determining $B$ from $A$:


  For $k=1,\dots,n$, determine the value of $B(k)$ by comparing each $A(i)$ to $A(k)$ for 
  $i=1,\dots,k$ and counting those that satisfy $A(i)&lt;A(k)$. 


This algorithm compares $A(1)$ to all others ($n-1$ times), $A(2)$ to $n-2$ others, etc. so the total number of comparisons is $\frac{(n-1)(n-2)}{2}$. But that's not the best we can do. For example, looking at $B(n)$, we don't have to do any comparisons! $B(n)=A(n)-1$ because it's the first $n$ natural numbers, and it’s guaranteed (regardless of the permutation) that the $n-1$ lower natural numbers will be there. What about $B(n-1)$? Instead of checking $A(1)$ through $A(n-2)$, we could just check $A(n)$. That is: 


  For $k=1, \dots,\frac{n}{2}$, use the algorithm above; for
  $k=\frac{n}{2},\dots,n$ use the reverse algorithm: determine $B(k)$ by
  setting it initially to $A(n)-1$ and then subtracting $1$ for each
  entry $A(i)$ for $i=k+1,\dots,n$ that is less than $A(k)$.


This would take $2\times\frac{(\frac{n}{2}-1) (\frac{n}{2}-2)}{2}=\frac{(n-2)(n-4)}{4}$ steps, which is still $O(n^2)$. Note also that in constructing $A$ from $B$, if $B(n)=A(n)-1$ then $A(n)=B(n)+1$.

But now for more finesse. If we’re allowed some additional space or sort in-place, we can sort the numbers as we’re comparing them. For example:
$$\begin{vmatrix}
  A &amp; 8 &amp; 4 &amp; 3 &amp; 1 &amp; 7 &amp; 2 &amp; 9 &amp; 6 &amp; 5 \\
  S &amp; 9 &amp; 8 &amp; 7 &amp; 4 &amp; 3 &amp; 2 &amp; 1 &amp; 6 &amp; 5 \\
  B &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 3 &amp; 1 &amp; 6 &amp;  &amp;  \\
\end{vmatrix}$$

Instead of checking all of them (or checking them in order), we could use binary search to determine each $B(k)$. However, the sorting still takes time $O(n\log n)$.