CODEWITHSUNDEEP
performancealgorithmbig-o
afancy
afancy

Reputation: 683

How to implement this O(1) algorithm for this 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!

Upvotes: 0

Views: 364

Answers (6)

Anders Lindahl
Anders Lindahl

Reputation: 42870

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

Upvotes: 4

Thomas
Thomas

Reputation: 88707

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.

Upvotes: 1

CloudyMarble
CloudyMarble

Reputation: 37566

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

Upvotes: 0

kan
kan

Reputation: 28951

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

Upvotes: 10

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272517

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!).

Upvotes: 0

Jens
Jens

Reputation: 25563

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

Upvotes: 14

Related Questions