8
$\begingroup$

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

$\endgroup$
0
8
$\begingroup$

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)$.

$\endgroup$
1
  • $\begingroup$ Thanks @Acccumulation. Of course it is "than". . (I wrote this thanks already once and it was deleted by somebody). $\endgroup$
    – zkutch
    Jan 10 at 19:22
3
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ He didn't say "at least linear time", so I'd argue the first part should be Θ(n) rather than Ω(n). $\endgroup$ Jan 10 at 2:39
  • 2
    $\begingroup$ @BernhardBarker Since it is an informal statement, it is hard to say what it precisely means. I felt that "needs" means "requires at least" $\endgroup$ Jan 10 at 5:53
  • 1
    $\begingroup$ @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. $\endgroup$ Jan 10 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.