No, I understand that there are n! permutations. Again you aren't actually searching through the permutations. You're running comparisons on the data to reduce

No, I understand that there are n! permutations. Again you aren't actually searching through the permutations. You're running comparisons on the data to reduce the set of possible permutations to the one it has to be. (pigeon hole principle) I believe my point still stands. You should be able to cut the search space in half with one comparison every single time, which should perform the same as a binary search. Edit: You are correct I made a mistake in my big O notation, it should be O(n log n).