patternMinor
Best-Case Running Time For Binary Search Tree Insertion
Viewed 0 times
caseinsertionsearchtimerunningbinaryfortreebest
Problem
The notion of best-case running time is kind of ambiguous for me. According to wikipedia, the definition of best case running time is:
The term best-case performance is used in computer science to describe the way of an algorithm behaves under optimal conditions. For example, the best case for a simple linear search on a list occurs when the desired element is the first element of the list.
According to this definition, the best case running time for BST insertion should be $O(1)$ [consider that we are inserting to the root node]. But different resources says different things, some claim that it is $O(\log n)$ [perfect balanced tree] and some others claim that it is $O(1)$ which one should I believe?
The term best-case performance is used in computer science to describe the way of an algorithm behaves under optimal conditions. For example, the best case for a simple linear search on a list occurs when the desired element is the first element of the list.
According to this definition, the best case running time for BST insertion should be $O(1)$ [consider that we are inserting to the root node]. But different resources says different things, some claim that it is $O(\log n)$ [perfect balanced tree] and some others claim that it is $O(1)$ which one should I believe?
Solution
Both! That is, if you are lenient with what "best-case" means. The best-case is the input for respectively run¹ of an algorithm which minimises runtime (for a given size). I guess that some of your sources refer to (asymptotically) optimal BST implementations, either them or you mixing up the notions.
These are the facts:
-
For any (reasonable) binary search tree implementation, the best-case insertion time is certainly $O(1)$ (for all sizes): all nodes are in the root's right subtree, the one to be inserted belong in the left.
-
An optimal binary search tree implemenentation has worst-case insertion time in $\Theta(\log n)$; it is height-balanced (examples include AVL- and Red-Black-trees).
These are the facts:
-
For any (reasonable) binary search tree implementation, the best-case insertion time is certainly $O(1)$ (for all sizes): all nodes are in the root's right subtree, the one to be inserted belong in the left.
-
An optimal binary search tree implemenentation has worst-case insertion time in $\Theta(\log n)$; it is height-balanced (examples include AVL- and Red-Black-trees).
- That's equivalent for deterministic algorithms; for nondeterministic ones you consider runs.
Context
StackExchange Computer Science Q#4723, answer score: 3
Revisions (0)
No revisions yet.