Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Running Time Analysis

The running time of the downward pass of the insertion algorithm is identical to that of an unsuccessful search (assuming the item to be inserted is not already in the tree). That is, for a B-tree of height h, the worst-case running time of the downward pass is

displaymath64961

The second pass of the insertion algorithm does the insertion and balances the tree if necessary. In the worst case, all of the nodes in the insertion path up to the root need to be balanced. Each time the InsertPair method is invoked, it calls FindIndex which has running time tex2html_wrap_inline64969 in the worst case. The additional time required to balance a node is O(M). Therefore, the worst-case running time of the upward pass is

displaymath64962

Therefore, the total running time for insertion is

displaymath64963

According to Theorem gif, the height of a B-tree is tex2html_wrap_inline64973, where n is the number of keys in the B-tree. If we assume that two keys can be compared in constant time, i.e., tex2html_wrap_inline63929, then the running time for insertion in a B-tree is simply tex2html_wrap_inline64979.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.