Eu não consigo te dar uma prova matemática rígida, mas eu afirmo com segurança que o que se pede é impossível. Para qualquer caso não trivial:
k < 0
(somente admite o vetor vazio com entrada, o retorno é zero)
a > k
(o retorno sempre é zero)
b < 0
(o retorno sempre é zero)
b < a
(o retorno sempre é zero)
a = 0 E b = k
(o retorno sempre é n
- assumindo que o tamanho do vetor pode ser determinado em tempo constante)
é possível se produzir dois vetores distintos:
V + [x]
, onde x ∈ [a,b]
V + [y]
, onde y ∉ [a,b]
que produzirão resultados diferentes se avaliados por essa função.
Suponha que exista um algoritmo com complexidade O(1)
. Então, para vetores de tamanho maior ou igual a n0
existe uma constante K
tal que o tempo de execução é menor ou igual a K
. Seja V
o vetor (um dos vetores?) cujo tempo de execução seja o maior de todos (i.e. K
), e cujo valor de retorno seja R
. Como esse algoritmo avaliaria V + [_]
?
- Se ele não executar nenhuma operação adicional às que ele já executou para avaliar
V
, então ele não pode dizer deterministicamente se o resultado é R
ou R + 1
- já que o elemento adicional pode ser pelo menos x
ou y
;
- Se ele executar uma ou mais operações adicionais, então seu tempo de execução é maior do que
K
(assumindo que uma operação possui tempo de execução maior que zero). Ou seja, o algoritmo não possui ordem de complexidade O(1)
, como pressuposto.
A propósito, isso também significa que - ao contrário do pressuposto - o vetor V
não era de fato aquele que possui o "maior tempo de execução de todos". Na verdade, tal vetor não existe - já que o conjunto de todos os vetores possíveis com elementos de 0
a k
é infinito (ainda que enumerável). Qualquer vetor que você eleger como "o maior" pode - conforme demonstrado - dar origem a um vetor cujo tempo de execução seja pelo menos uma operação elementar maior que ele.
O melhor algoritmo que soluciona esse problema terá complexidade de O(n)
. É inevitável que todos os elementos do vetor sejam visitados ao menos uma vez - seja para comparar, seja pra incluir numa contagem, seja para ser objeto de uma operação aritmética. A menos que haja alguma "pegadinha" que eu não esteja vendo, esse exercício não tem solução...