Find First Place Where F <= 0 in O(log n) Time

[Jcampuzano2]

Homework Statement

Consider a strictly decreasing function F: ℕ → ℤ. We want to find the "first place where f is at or below the horizontal axis." Assume we can compute ƒ(i) for any input i in constant time. Clearly, we can solve the problem in O(n) time by evaluating ƒ(1), ƒ(2), ƒ(3),... until we see a non-positive number. Give an O(log n) algorithm.

Homework Equations

The only given is that ƒ(0) > 0.

The Attempt at a Solution

I'm a little confused on this problem. I don't have a finite input size, so I can't just access the last element in an array like I'm used to on algorithm problems. My only guess so far is that I could could pick a random number and test whether it is less than 0. If it is, then I can say that that can be considered the last element in an set, and perform a binary search to find the first place where the value is less than 0, but what if it takes greater than O(log n) time just to find this initial value?

So for example I test say f(100). if that is less than 0, then my input set can be say 0, 1, ... 100. and do a binary search using this as input. Would this be the correct way to go about this? It's literally the only way I can think of.

 

[DrClaude]

I'm a bit confused. If an algorithm can be said to be O(n), it means that n is defined, that there is a number of input data. If you indeed let i not be constrained, then saying that an algorithm is O(n) doesn't make sense to me.

Could it be that n is constrained by the largest ℕ that can be expressd depending on the data type of i?

 

[Jcampuzano2]

I'm a bit confused. If an algorithm can be said to be O(n), it means that n is defined, that there is a number of input data. If you indeed let i not be constrained, then saying that an algorithm is O(n) doesn't make sense to me.

Could it be that n is constrained by the largest ℕ that can be expressd depending on the data type of i?

That's part of where my confusion comes from as well. This problem isn't given with any data types in its context. I might just have to ask for more info on this one. The only part of the problem I left out because it was explained in the problem is the following sentenct:

We want to find

n = min{ i ∈ ℕ : ƒ(i) ≤ 0} .

But that was explained in the next sentence "first place where f is at or below the horizontal axis." Maybe that helps, but I don't think it does. Correct me if I'm mistaken.

 

[DrClaude]

Maybe that helps, but I don't think it does.

I'm still as confused. And the more I think about it, the more I'm convinced that the question only makes sense if the value of i is bounded.

 

[rezeew]

Your approach is on the right track, but there is a more efficient way to do it in O(log n) time.

One possible solution is to use a modified binary search. Start by choosing a random number k and evaluating ƒ(k). If ƒ(k) is less than or equal to 0, then k is the first place where ƒ is at or below the horizontal axis. If ƒ(k) is greater than 0, then we know that the first place where ƒ is at or below the horizontal axis must be to the left of k. So we can recursively apply the same process on the left half of the input set (from 1 to k-1). This will continue until we find the first place where ƒ is at or below the horizontal axis.

The key here is that at each step, we are dividing the input set in half, so the time complexity will be O(log n). This is because each time we divide the input set in half, we are essentially reducing the size of the input set by half. So after k steps, the input set will have a size of n/2^k. Solving for k, we get k = log n, which gives us the time complexity of O(log n).