1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Design an algorithm -- find the first place where f is at or below the horizontal axis

  1. Jan 27, 2015 #1
    1. The problem statement, all variables and given/known data

    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.

    2. Relevant equations
    The only given is that ƒ(0) > 0.

    3. 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.
  2. jcsd
  3. Jan 27, 2015 #2


    User Avatar

    Staff: Mentor

    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?
  4. Jan 27, 2015 #3
    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.
  5. Jan 27, 2015 #4


    User Avatar

    Staff: Mentor

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted