In the question in this video about quicksort luckily picking the median in each recursive call. Tim Roughgarden, the presenter, says at 11:22
Partition needs really linear time, not just $O(n)$ time.
What does he mean here? I thought linear time is $O(n)$. Does he mean $\Theta(n)$ or something else? I see how partition in quicksort here would be $\Theta(n)$ but I don't get the part that says "not just $O(n)$ time".