2
$\begingroup$

In the Wikipedia's Binary search tree, one can read

Traversal requires $O(n)$ time, since it must visit every node.

Since it is question of a lower bound, shouldn't we write

Traversal requires $\Omega$(n) time, since it must visit every node.

Is the $O(n)$ statement here even correct?

Improve this question
$\endgroup$
1
  • 4
    $\begingroup$ The original statement is meaningless. It exhibits a common misconception about asymptotic notation. $\endgroup$
    – Yuval Filmus
    Commented Apr 19, 2021 at 9:24

2 Answers 2

Reset to default
1
$\begingroup$

If you consider the problem Tree traversal, then the correct answer is indeed:

Traversal requires $\Omega$(n) time, since it must visit every node.

We are here talking about requirement and lower bound, as in "what is necessary".

If you want to talk about common algorithms for tree traversal, then it is true that they also have a complexity $O(n)$, which means that it is an upper bound in "what we can do".

However, since your question, the wikipedia page was modified and the current sentence does not really make any sense (basically "Tree traversal is $O(n)$. Since it is also $O(n)$, it is optimal.").

Improve this answer
$\endgroup$
0
$\begingroup$

Traversal of a binary tree is $O(n)$, $\Omega(n)$, and $\Theta(n)$. All three are correct.

Big-O is an upper bound, Big-Omega is a lower bound, and Big-Theta is a "tight" bound.

Big-O notation is often used in a non-formal context even when a stronger claim (i.e. $\Theta(n)$) can be made. Big-Omega alone isn't the most helpful metric. We're often much more concerned with the upper bound.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Only $\Omega(n)$ is correct, since you could implement a bad algorithm for traversal. It is usually $O(n)$ because we know ways to do it efficiently, but it is not necessary. $\endgroup$
    – Nathaniel
    Commented Apr 19, 2021 at 17:59
  • $\begingroup$ @Nathaniel No. When we look at complexities we don't attempt to describe all contrived bad implementations. Same reason we don't say traversal is O(n!^n) and Omega(1). $\endgroup$
    – user135438
    Commented Apr 19, 2021 at 18:03
  • 1
    $\begingroup$ I will give more details on an example: sort by comparisons. It is well known that a lower bound on sorting by comparisons is $\Omega(n\log n)$. Is it true that sorting is $O(n\log n)$? No, because there are several algorithm that are not in $O(n\log n)$ (insertion sort, even quicksort). Is it true that we can solve sorting in $O(n\log n)$? Yes, because there are algorithms to do so (merge-sort or heapsort for example). Is quicksort a bad implementation even though it is $\Omega(n^2)$ worst case? No, because is it $\Theta(n\log n)$ average case. $\endgroup$
    – Nathaniel
    Commented Apr 19, 2021 at 18:20
  • $\begingroup$ @Nathaniel My man you are missing the point. There is no reasonable way to traverse a binary tree in worse than O(n) time. $\endgroup$
    – user135438
    Commented Apr 19, 2021 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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