I can do time O(n^2), where n is the length of the list. Perhaps the “extremely fast” algorithm you have is O(n log n)? Surely O(n) must be impossible.
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.
I can do time O(n^2), where n is the length of the list. Perhaps the “extremely fast” algorithm you have is O(n log n)? Surely O(n) must be impossible.
O(n log n) would be nice, but you can do even better :-)
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.