Algorithm time optimization for a very simple algorithm

Question

I have this piece of code I developed in an algorithm. It finds the first element of an array that is greater than a given one for a fixed amount. It iterates using all the array elements as a comparing item and print the result for any given comparing item

for(i=0; i<N; i++) {
    for (t = i + 1; t < N - 1; t++) {
        if (H[t] - H[i] > VSQR)
            break;
    
    }
    printf("%d ", t - 1); // print the result
} 

The algorithm results too slow for big arrays, but I cannot find any optimization.

question from:https://stackoverflow.com/questions/65939543/algorithm-time-optimization-for-a-very-simple-algorithm

Answer 1

The idea of the O(nlogn) algorithm:

First we need to realize that only the heights we can see from some position matter (assuming bigger heights hide smaller heights, similar to the sky scraper logic puzzle). That's because if an height is high enough and meets our constraints we would stop there and if it isn't high enough then surely the smaller heights behind it don't matter.

If we only look at the heights that matter, they will be ordered from smallest to highest. So if we only have those heights we can do a binary search on them. We get the heights that matter by going backwards and discarding all heights behind us that are smaller or equal to the current height.

After that we do a binary search on the remaining heights to find the correct one.

Finally we insert the current height into the heights that matter.

We can implement this using arrays. The heights that matter will be stored in decreasing order (highest first, lowest last). This means that to discard all heights smaller or equal to the current one we can do a binary search and just set the size to a different value, so all smaller ones are not in our scope any more. Then we can do a binary search on that array to find the correct height. We use a second array just to store the index of the heights that matter, so we can get the result immediately. Finally to insert the current height we just add it at the end of the heights array, because it is now the smallest height that matters and the array is sorted in decreasing order.

The time complexity is O(nlogn) because the binary search to find the values to discard is O(logn) and the binary search to find the result is also O(logn). We do this n times. O(n) * (O(logn) + O(logn)) = O(2nlogn) = O(nlogn)

So it could be implemented like this:

int[] heights = new int[N]; // we need to add at most N values
int[] indices = new int[N]; // therefore just make array length N
int[] result = new int[N];
heights[0] = H[N - 1];
indices[0] = N - 1;
result[N - 1] = N - 1;
int size = 1;
for (int i = N - 2; i >= 0; i--) {
    size = binarySearch(heights, H[i], 0, size) + 1; // discards all values <= H[i]
    if (size == 0) {
        result[i] = N - 1;
    } else {
        int x = binarySearch(heights, H[i] + VSQR, 0, size); // find result
        result[i] = x < 0 ? N - 1 : indices[x] - 1;
    }
    heights[size] = H[i]; // add height at the end
    indices[size] = i;
    size++;
}

// binarySearch(array, value, from, to) returns the index of the smallest 
// number which is greater than 'value' in the range 'from' <= i < 'to'
// or returns -1 if there is none

---

Old answer, before realizing AVL tree is not needed:

It is possible to get O(nlogn) instead of O(n^2) by using an AVL tree and going backwards.

The height value is used for the positioning in the tree, but along with this value we also store the index in the node. Also create an array for the results.

Then for each height (going backwards from the last one until the first one) do the following:

Remove all items <= H[i] from the tree. Find and set the result using the tree (that's why we also need the index in the node, so we can get the result easily). The value we are looking for is the smallest value > H[i] + VSQR (if the tree is empty or if there is no value big enough then the result is N - 1). Insert H[i] into the tree.