Insights Blog
-- Browse All Articles --
Physics Articles
Physics Tutorials
Physics Guides
Physics FAQ
Math Articles
Math Tutorials
Math Guides
Math FAQ
Education Articles
Education Guides
Bio/Chem Articles
Technology Guides
Computer Science Tutorials
Forums
Intro Physics Homework Help
Advanced Physics Homework Help
Precalculus Homework Help
Calculus Homework Help
Bio/Chem Homework Help
Engineering Homework Help
Trending
Featured Threads
Log in
Register
What's new
Search
Search
Search titles only
By:
Intro Physics Homework Help
Advanced Physics Homework Help
Precalculus Homework Help
Calculus Homework Help
Bio/Chem Homework Help
Engineering Homework Help
Menu
Log in
Register
Navigation
More options
Contact us
Close Menu
JavaScript is disabled. For a better experience, please enable JavaScript in your browser before proceeding.
You are using an out of date browser. It may not display this or other websites correctly.
You should upgrade or use an
alternative browser
.
Forums
Homework Help
Engineering and Comp Sci Homework Help
Find First Place Where F <= 0 in O(log n) Time
Reply to thread
Message
[QUOTE="Jcampuzano2, post: 4989395, member: 462099"] [h2]Homework Statement [/h2] 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. [h2]Homework Equations[/h2] The only given is that ƒ(0) > 0. [h2]The Attempt at a Solution[/h2] 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. [/QUOTE]
Insert quotes…
Post reply
Forums
Homework Help
Engineering and Comp Sci Homework Help
Find First Place Where F <= 0 in O(log n) Time
Back
Top