title: find total number of (i,j) pairs in array such that i<j and a[i]>a[j]
body: <p>As mentioned in the question ,need to find total number of (i,j) pairs in array such that </p>
  
  <pre><code>(1) **i&lt;j** 
  (2) **a[i]&gt;a[j]**
  </code></pre>
  
  <p>where i and j are indices of the array . There are no space constraints .</p>
  
  <p>My question is</p>
  
  <pre><code> 1) Is there any approach which takes less than O(N^2) time?
   2) if so what is least complexity ?
   3) How do we prove that ? 
  </code></pre>
  
  <p>I hope i'm clear with the question .</p>
  
  <p>My approach is as follows</p>
  
  <p>One way of doing the question is using brute fore which takes O(N^2) time .</p>
  
  <p>But I think that there should be a better optimised solution to this question at-least O(NlogN) sollution .The reason for my intuition is as follows</p>
  
  <p>Intuition 
      <code>1)   For sorting an array in ascending order conditions we have are : for i&lt;j , a[i]&lt;a[j] which is similar to my question  . I also read that sorting has lower bound of  Omega(n log n) . So my question should also have  Omega(n log n) . I may be completely wrong if so please correct me .</code></p>
  
  <p>My second intuition is:</p>
  
  <p>Suppose we have an array of elements as follows : 4,9,7,3,2,1,8,12</p>
  
  <p>we calculate above condition <code>i&lt;j , a[i]&gt;a[j]</code>  for element 4 ,as i=0 points to 4 ,the possible values for j are 3,4,5 .since a[0]>a[3],a[0]>a[4],a[0]>a[5] ,so my total no of (i,j) pairs for now is 3 .
   Next time when I increment i(index) to 1,the possibles values of j are 2,3,4,5,6 . But we should use the fact that when i=0 (when a[i]=4) we have computed 3 elements less than a[i=0] which is in turn less than a[i=1] , so  i will not compare 9 with 3,2,1 (To remove unnecessary computations ).If we can remove unnecessary computations then we can reduce complexity to something less than O(N^2) or else no solution less than O(N^2) exists.But if solution exists then how do we do that.I tried making graph but my efforts are futile .</p>
  
  <p>Approach 1)<code>In-order to obtain O(nlogn) complexity I think we need to tweak around quick sort or merge sort to get solution but problem here is, if we sort the array we loose the actual positions of elements.</code>  </p>
  
  <p>Approach     <code>2)In-order to get solution in O(NlogN) time I think using tree we may get the optimised sollution . I didn't get any clue.</code></p>
  
  <p>Approach 3)<code>If there exists any O(N) time algorithm it should be with hashing . But in this case simple hashing doest work .</code></p>
  
  <p>So please let me know which of the above intuitions or approaches are correct (If correct which approach will lead to optimised sollution and how). </p>