Of course, for low values of N the constants dropped from the big-O notation start to matter. For very small values of N and a random-access input, even an O(N^2) approach may be optimal (for each input element, check for equality against previous elements of the input, output if no hit).