Complexity of algorithm to find number of elements > element index i in an array

The question is:

Given an array of size N, arr, create another array whose index i = number of elements in sub-array(arr, i+1, N-1) that are greater than arr[i].

Eg. if input array is,
5 3 9 8 2 6
output array is
3 3 0 0 1 0

O(N^2) is simple just two for loops.

I think a O(N*logN) is possible by starting from last element and adding each element to a height-balanced BST with a size element.

Any thoughts on if we can do O(N)?

Your problem is very related to that of computing the number of inversions in a permutation, or (equivalently) the Kendall tau distance between two permutations; this is the sum of your vector. In fact, your vector (with a very superficial change in the definition) is known as the inversion vector.

There is a classical data structure of Dietz that can be used to compute the inversion vector in time $O(n\log n/\log\log n)$; the $O(n\log n)$ solution you mention is the baseline here. Fredman and Saks proved a matching lower bound showing that the time complexity of Dietz's data structure is optimal. Computing the insertion vector can however be done faster: Chan and Pătraşcu give an $O(n\sqrt{\log n})$ algorithm (see under "Offline dynamic ranking and selection").

StackExchange Computer Science Q#63626, answer score: 8