New answers tagged time-complexity
2
After some more searching, I managed to find a proof in these lecture notes [1]. The proof goes via Yao's principle and the lower bound is n/3. If someone knows of a published paper or a book that I may cite for this fact, I am still interested.
[1] https://people.cs.rutgers.edu/~sa1497/courses/cs514-s20/lec3.pdf
Top 50 recent answers are included