Divide and conquer algorithm

Question

Let $L_{1},L_{2},...,L_{n}$ be a sequence of numbers, and let $i, j$ be the indexes such that $1 \leq i<j \leq n$.

I need to find the amount of numbers that satisfy $L_{i}<2 L_{j}$ with time complexity $\mathcal O\,(n \cdot log(n))$

Answer 1

As the title suggests you will need to apply a divide and conquer idea. So the difficult part is the merge part. Let the following pseudo-code

Function solve
Input : L[1...n] a list
Output : Sorted copy of L and the number of indexes (i,j) such that i<j and L[i]<2L[j]
If n == 1:
   return L, 0
A, m := solve(L[1...n/2])
B, p := solve(L[n/2+1...n])
i := 1
j := 1
t := 0
u := 0
While(i <= len(A) and j <= len(B)):
   if A[i] < 2 * B[j]:
      i := i+1
      t := t+1
   else:
      j := j+1
      u := u+t
While(j <= len(B)):
   j := j + 1
   u := u + t
C = merge(A,B) //to have a sorted copy of L
return C, m+p+u

Since the merge is done in $\mathcal O(n)$ so the complexity is $\mathcal O(n\log(n))$.