I had the following question on my data structures midterm.
What is the best-case performance of the insertion operation in a 2-3 tree, in Big-O notation?
I gave as answer:
O(1), assuming that the tree is empty
It was marked as wrong. The answer key says O(log n).
When a question asks for the best-case runtime, are we not allowed to assume that the tree is empty beforehand?
Big O notation is about ever larger input sizes and how that size affects running time. That means you are not allowed to put a ceiling on the input size. If the analysis is limited to being 0 (i.e. an empty tree), you don't get an indication of asymptotic complexity. It is essential that is allowed to be a large value, without limit.
"Worst case" and "best case" can be meaningful if there is still some variation possible in the input for a given . With a B-tree data structure there is such variation: for instance, when two B trees have the same number of values (), their number of nodes (blocks) and heights may still be different. Such variation may influence the performance of the algorithm. For instance, the B-tree insertion algorithm will have less work to do when no node has to be split.
So when you're asked to give the best case complexity, you cannot put a limit on , but (for any ) you should assume the optimal shape of the tree: optimal for the algorithm to be most efficient.
Still, it may turn out that even in such best cases the complexity does not improve when comparing it with worst cases. For instance, if you would conclude that in best case there is about half the work to be done compared with the worst case, then in terms of time complexity we must conclude that best case and worst case complexity are equal.
In the case of the B-tree insertion algorithm both the best case and worst case time complexity is O(log).
