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?

$\endgroup$
1
  • 4
    $\begingroup$ The original statement is meaningless. It exhibits a common misconception about asymptotic notation. $\endgroup$ Apr 19 '21 at 9:24
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.").

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

$\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
    Apr 19 '21 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$
    – qz-
    Apr 19 '21 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
    Apr 19 '21 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$
    – qz-
    Apr 19 '21 at 18:54

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.