The Number of Inversions in an Array

Problem:
Let \(A[1...n]\) be an array of \(n\) distinct numbers. If \(i \lt j\) and \(A[i] \gt A[j]\), then the pair \( (i,j) \) is called an inversion of A. Determine the number of inversions given an array of distinct numbers.

Solution 1:
Naive approach. There are \( \frac{n(n-1)}{2} \) number pairs in an array of size \(n\), and check one by one. The time complexity is \(O(n^2)\).

We can have a better solution for this problem, which is proposed as below.

Solution 2:
Divide-and-conquer. This strategy works in similar way to merge-sort, and bears time complexity \(n\log n\).

Various Implementations of pow(x, y)

In this post, I discuss the implementation of function
double pow( double, int ).

Let's first consider the most simple case: y is a positive integer.
The naive and straightforward approach is working with a loop like following.

Next, we need consider all possible integers for y.

We can write a recursive function to calculate x raised to the power y.

The time complexities for all above 3 implementations are \(O(n)\). Use of a temporary variable would help.

Now, the time complexity reduces to \(O(\log n)\). How about non-recursive version? Yes, we can do it.

Actually, we can have one more implementation with bit operations!! Sounds amazing!