I can not give you a rigid mathematical proof, but I say with certainty that what you ask for is impossible. For any non-trivial case:
-
k < 0 (only accepts empty vector with input, return is zero)
-
a > k (return is always zero)
-
b < 0 (return is always zero)
-
b < a (return is always zero)
-
a = 0 E b = k (the return is always n - assuming that the size of the vector can be determined in constant time)
It is possible to produce two distinct vectors:
-
V + [x] , where x ∈ [a,b]
-
V + [y] , where y ∉ [a,b]
which will produce different results if evaluated by this function.
Suppose there is an algorithm with O(1) vel complexity. Then, for vectors of size greater than or equal to n0 there is a constant K such that the execution time is less than or equal to K . Let% be the vector (one of the vectors?) Whose execution time is the largest of all (i.e. V ), and whose return value is K . How would this algorithm evaluate R ?
- If it does not perform any additional operations it has already performed to evaluate
V + [_] , then it can not say deterministically whether the result is V or R - since the additional element can be by less R + 1 or x ;
- If it performs one or more additional operations, then its execution time is greater than
y (assuming an operation has execution time greater than zero). That is, the algorithm has no order of complexity K , as assumption.
By the way, this also means that - contrary to the assumption - the O(1) vector was not actually the one with the "longest execution time of all". In fact, such a vector does not exist - since the set of all possible vectors with elements of V to 0 is infinite (albeit enumerable). Any vector that you choose as the "largest" can - as shown - give rise to a vector whose execution time is at least an elementary operation greater than it.
The best algorithm that solves this problem will have complexity of k . It is inevitable that all elements of the vector are visited at least once - whether for comparison, whether to be included in a count, or to be the subject of an arithmetic operation. Unless there is some "catch" that I can not see, this exercise has no solution ...
