[33] Consider the 1-tape Turing machine as in Section 6.1.1, page 450. Let the input be n/ log n integers each of size O(log n), separated by # signs. The element-distinctness problem is to decide whether all these integers are distinct. Prove that the element-distinctness problem requires Ω(n2/ log n) time on such a 1-tape Turing machine.

Comments. A similar bound also holds for 1-tape nondeterministic Turing machines. Source: [A. L´opez-Ortiz, Inform. Process. Lett., 51:6(1994), 311–314].