정렬 알고리즘의 한계는 무엇인가요?

안녕하세요
학부생으로 오늘 알고리즘 시험을 보고 나왔습니다

강의시간에 맨날 졸다가 나온 결과로
한 문제를 제맘대로 풀고 나왔는데요
궁금한게 있어서 질문으로 올립니다

문제는 이거입니다
sorting algorithm이 O(n)이 될 수 없음을 증명하시오

분명 강의 시간에 이런 내용으로 시작했던게 기억나는데
그 이후 제가 꿈나라속에서 허우적대느라 강의끝나는것밖에 기억에 없네요ㅠㅠ

게다가 웹 검색을 좀 해봤는데
there is no, On, sorting algorithm, limit 등으로 검색해도 안나와서 못찾았습니다

그래서 의문을 해결하고자 글을 올립니다

제 예상으로는
quick sort나 heap sort같은 O(nlogn) 정도의 알고리즘이 한계일거라 생각하고
답을 찾아가는 형식으로 풀어봤습니다

data 1 -> 최대 검색시간 : 0 | 최소 검색시간 : 0 & 입력시간 : 1
data 2 -> 최대 검색시간 : 1 | 최소 검색시간 : 1 & 입력시간 : 1
data 3 -> 최대 검색시간 : 2 | 최소 검색시간 : 1 & 입력시간 : 1
data 4 -> 최대 검색시간 : 3 | 최소 검색시간 : 1 & 입력시간 : 1
data 5 -> 최대 검색시간 : 4 | 최소 검색시간 : 1 & 입력시간 : 1

이것까지 써둔 뒤에
시간이 없어서 그냥 나왔는데요

이걸로는 무언가 접근이 안되는거 같기도 하고..

혹시 자료 있으신 분, 혹은 알고 계시는 분 있으시다면 가르쳐주세요 ㅎㅎ