3 ms·
You don't need to compare permutations you reduce the set of possible permutations until you reach the one that must be the answer. Theoretical performance shou
by pg_bot 5y ago
You don't need to compare permutations you reduce the set of possible permutations until you reach the one that must be the answer. Theoretical performance should be O(log n)
- saagarjha 5y agoNo, I understand your algorithm, I’m just saying that you’ll start with n! permutations and halve that with each step. This will require log(n!) steps.
- tim-peters 5y agoSorry, nope. There aren't n permutations you're searching through, but the factorial of n to search through. That's the heart of the information-theoretic proof that no comparison-based sorting algorithm can do better, on average, than needing a number of comparisons equal to the base-2 logarithm of the factorial of n. Which, as already said, is O(n log n).
- pg_bot 5y agoNo, 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).