- #1

- 5

- 0

## 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.