Is it possible to check in java if an array is Sorted or not with O(1) worst time complexity?

CodePudding user response：

It's impossible to have a correct algorithm with better than O(n) complexity. Let's prove it by contradiction. If are we given an algorithm with better than O(n) complexity we can provide a test array

{1, 2, 3, ..., n}

where n is large enough so the algorithm has to skip some items (note, that if algorithm inspects all items it has at least O(n) time complexity). If algorithm returns false it's incorrect; if it returns true we have to create one more test. Let m be the item which is not inspected:

{1, 2, 3, ... m - 1, m, m   1,... n}
                     ^
Not inspected by the algorithm.

Let's create the test array as it was before but change m into n 1

{1, 2, 3, ..., m - 1, n   1, m   1, ... n}
                        ^
           we changed m into n   1 

Since m is not inspected, the algorithm returns true which is now incorrect. So the arbitrary algorithm with time complexity better than O(n) is incorrect, or put it in different way: there are no correct algorithms with better than O(n) time complexity.