# Isn't linear time O(n)?

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".

Usually we call statement $$A$$ stronger than $$B$$ when $$A$$ implies $$B$$: $$A \Rightarrow B$$ (weaker-stronger). In other words, $$B$$ is weaker than $$A$$.

When the presenter is speaking about linear time for partition, this is a stronger statement than $$O(n)$$ time. All linear functions are in $$O(n)$$, but it also contains non-linear functions.

For example: $$\sin n, \frac{1}{n}, \sqrt{n}$$ are all in $$O(n)$$, but they are not linear. As was written in a comment, $$O(n)$$ is the set of functions bounded by linear functions, but not the set of only linear functions.

To be linear gives more information than to be in $$O(n)$$, to be in $$\Omega(n)$$, even to be in $$\Theta(n)$$.

• Thanks @Acccumulation. Of course it is "than". . (I wrote this thanks already once and it was deleted by somebody). Jan 10 '21 at 19:22

The partition needs really linear time

Here, the presenter meant that partition takes $$\Omega(n)$$ time.

not just $$O(n)$$ time

Here, the presenter meant that this is a loose or weak statement. A stronger statement would be that partition takes $$\Omega(n)$$ and $$O(n)$$ time, which is equivalent to $$\Theta(n)$$, as you are saying.

• He didn't say "at least linear time", so I'd argue the first part should be Θ(n) rather than Ω(n). Jan 10 '21 at 2:39
• @BernhardBarker Since it is an informal statement, it is hard to say what it precisely means. I felt that "needs" means "requires at least" Jan 10 '21 at 5:53
• @BernhardBarker: Given that we already know it's possible in O(n), saying something that means "at least linear" amounts to saying that a good algorithm will run in Θ(n). I find the whole thing a strange and confusing way of expressing the point, but maybe it made more sense in context. And if spoken in a video, maybe would be something they would have changed if doing over again but didn't want to re-record a segment. Jan 10 '21 at 15:14