How to implement this O(1) algorithm for this question?

Question

I have variable x, and the functions f1(x), f2(x), .... fn(x) (n can be up to 1 million). The values of these functions are 1 or 0. So, how to write the algorithm,which can quickly pick up the functions which return 1? thanks.

Here I present mine. It has O(n) time complexity, which is not efficient enough.

List funHaveTrueValues = new ArrayList();
for (int i=1; i<=n; ++i){
 if (fi(x)==true){
 funHaveTrueValues.add(fi);
 }
 }
}

Could anybody propose O(1) algorithm? thanks!

• Oliver Charlesworth: What makes you think there is an O(1) approach?
• Paul R: Why are you iterating over a range of n+1 if you only have n functions ?
• Nanne: What is the input? This might be just wordplay, but if you input is x, and your functions f1...fn are considered part of the input your algorithm is O(1) for all and every x if fi is constant for all X.
• rossum: Use a parallel machine with n processors. With the information given, you have to check all n functions.

Answer 1

Unless you know a bit more about the functions than you are telling us, there cannot be an O(1) algorithm for that. You have to look at every function's output at least once, making every algorithm for this problem run in Ω(n).

• afancy: I think I might have to use multithreads to computes the values of all the functions in parallel, then pick up the functions which return true value.
• kan: To use n threads you have to launch n threads which takes O(n) steps!
• Nick Johnson: @kan Nitpick: You can launch two threads, and have each of those launch two threads, and so forth, in O(log n) steps for each thread. ;)

Answer 2

There is Grover's Algorithm which does it in O(sqrt(n)) but it requires a quantum computer.

• Oliver Charlesworth: Even once you've purchased your quantum computer, this algorithm isn't guaranteed to give you the correct result...

Answer 3

If you can assume that each f is O(1), then making at most 1.000.000 calls to them still has a constant upper bound. Thus I believe your sketched approach is O(1), if you limit it to 1.000.000 calls.

Edit

As I got a few downvotes on this, I' try to clarify the reasoning. Given the information at hand, there is no faster way to solve this than to evaluate all f. If the question is really "Is there a faster/more clever way to do this?" then the answer is (as many have answered) no.

If the question however is in the style of "I got this question on a complexity theory test" (or similar) then it might be a "gotcha!". This is the case I aimed for with my answer. In the generalized problem (with n functions, no limits) the time complexity is O(n) granted that each function behaves as an O(1) oracle. By introducing the roof of 1.000.000 functions, time complexity gets a constant upper bound of O(1000000 * 1) = O(1).

• Karoly Horvath: it's ridiculous. I have an O(N!) algorithm but because I run it on a 32bit machine my algo is really limited to N<4G, so it's O(1). Right?
• Oliver Charlesworth: +1 from me: I was just about to update my answer to make this suggestion!
• Karoly Horvath: Oh come'on you do asymptotic analysis which depends on a variable (here: N). in N that algo is O(N). If you limit N your program will finish in O(1), but this doesn't change the fact that the algo itself is O(N). What you're saying is anything (which isn't an infinite loop) is O(1) on PC because basic types are limited and if not then memory is limited.
• Anders Lindahl: @yi_H: Yes, in the general case (and for practical purposes) you are correct - I wouldn't have answered this if the OP hadn't stated an upper bound. We don't know if the question is practical or about technicalities of complexity.
• Steve Jessop: +1 for a silly answer to a silly question :-) It's the only way that the questioner's desired O(1) can be achieved (well, not so much "achieved" as "weasel-worded"), so if the answer is unacceptable it's only because the question is impossible. Serves the questioner right for bandying about terminology imprecisely - since n is bounded in the question, O(n) doesn't mean what the questioner thinks it means.

Answer 4

If x does change you'd need to evaluate every function anyways, so it would still be O(n). You might, however, determine for which x the result might be 0 or 1 (if it's possible to get something like: x <= y always results in 0, x > y is always 1) and store those thresholds. You'd then only have to evaluate the functions once and later just check x against the calculated thresholds. Note that this highly depends on what your fn(x) really does.

Thus the key to something O(1) like might be caching, as long as the fn(x) results are cacheable with reasonable effort.

Answer 5

You must evaluate each function at least once, and there are n functions. Therefore you cannot do better than O(n) (unless of course you precompute the output for all possible inputs and store it in a table!).

Answer 6

this is not possible, you have to run your functions for all n elements anyway, which means n-functions