# An algorithm with O(√n) complexity

·

## Given two crystal balls that will break if dropped from a high enough distance, determine the exact spot in which it will break in the most optimised way.

Prerequisite: Binary Search, Big-O Notation

Let’s consider the collection of various distances as a boolean array. In this array, an entry is `true` if the crystal ball will break at that distance, and `false` if the ball will not break. The `false` and `true` entries are contiguous, so the array will be like this, `[false, false, false, true, true]` or `[false, true, true]`, and `true` entries will always come after `false` entries (if `true` entries exist). We have to find the index of the first entry where the value is `true`.

### Linear Search will work but needs O(n) time.

• We’ll go through each entry and check if it’s `true`. In the worst case, only the last entry is `true`, and we’ll have to go through the whole array.
``````// O(n)
function solution(breaks: boolean[]): number {
for (let index = 0; index < breaks.length; index++) {
if (breaks[index]) return index;
}

return -1;
}
``````

### Binary Search will also need O(n) time.

• Consider an array like this `[false, false, false, true, true]`. In typical Binary Search fashion, let's halve the array and check the entry.

1. If the entry is `true`, how can we determine if this is the first `true` entry? We have to go backwards in the array from our current position until we find a `false` and the last `true` index is our result.

2. If the value is `false` we’ll move to the right half. We keep doing this until we find a true value, and then move to step 1.

• To measure the complexity, let’s assume a worst-case where all the values are `true`. For such an array of length 1000, the loops will run exactly 502 times. For 10000, it becomes 5002, and it goes on proportionately. So we can see that the number of iterations is roughly half, so it’s O(n/2), which is equivalent to O(n) without the constant factor.

``````// O(n/2) => O(n)
function solution(breaks: boolean[]): number {
let lo = 0;
let resultIndex = null;

while (lo < breaks.length - 1) {
const mid = Math.floor(lo + (breaks.length - lo) / 2);
if (!breaks[mid]) {
lo = mid;
continue;
}

resultIndex = mid;
while (breaks[resultIndex]) {
--resultIndex;
}
break;
}

return resultIndex ? resultIndex + 1 : -1;
}
``````

### Optimised Linear Search can do this in O(√n) time!

• Strategy: What if, unlike linear search where we go over the entries one by one, we jump a certain distance in each iteration, and then go back a bit if we already crossed the first `true` entry? The happy path would look like this,

• We’ll start iterating from the beginning of the array and jump a certain amount (√n) in each iteration.

• If we find a `true` entry, we know for sure that the entry itself or some other entry before it will be the first `true` entry.

• We iterate from our current index to the last iteration index where we found the `false` entry, and the first `true` entry will be somewhere in between.
• Example: Let’s say we have an array like `[false, false, false, true, true, true]`. Here, if we jump by √n each time from the `0th index`, we’ll find a `true` entry at `4th index` in the `2nd iteration`. As the entry itself isn’t the first `true` entry, we can iterate backwards from `4th index` to the last `false` index. This inner iteration will run √n times at worst-case, but we'll find the result, guaranteed!

• Complexity: As we’re jumping √n distance each time, the maximum number of iterations can be `n/√n`. If the jump is successful, that is we’ve found a `true` value, then we’re iterating a partial array with a length of √n. So the total number of iterations is `(n/√n) + √n`, which denotes the complexity is `O(√n)`. This is significantly less than the Linear/Binary Search approach.

``````// O(√n)
function solution(breaks: boolean[]): number {
const jumpAmount = Math.floor(Math.sqrt(breaks.length));

for (
let outerIndex = 0;
outerIndex < breaks.length;
outerIndex += jumpAmount
) {
if (!breaks[outerIndex]) continue;
for (
let innerIndex = outerIndex;
innerIndex >= outerIndex - jumpAmount;
innerIndex--
) {
if (!breaks[innerIndex]) {
return innerIndex + 1;
}
}
}

return -1;
}
``````