Just to check we are formalizing in the same way, do you agree that O(n) is a lower bound? Because the list [1,2,...,n] has longest credible prefix of length n, but if we reduce any of the first n-1 elements by 1 then the length of the longest credible prefix is reduced. So we at least have to spend O(n) time looking at the first n-1 elements.
Just to check we are formalizing in the same way, do you agree that O(n) is a lower bound? Because the list [1,2,...,n] has longest credible prefix of length n, but if we reduce any of the first n-1 elements by 1 then the length of the longest credible prefix is reduced. So we at least have to spend O(n) time looking at the first n-1 elements.
Yes, O(n) is a lower bound.