Search code examples
time-complexityb-tree

Why B Tree complexity is O(log n), it is not a binary tree


According to Wiki and GFG the search/insert/delete time complexity of a B Tree is O(log n). A B Tree can have > 2 children, i.e. it is not a binary tree. So I don't understand why it is log n -- shouldn't it be faster than log n? For example search should be worst case O(h) where h is the height of the tree.


Solution

  • B-Tree is a generalization of Binary Tree where each node can have more than 2 children. But it is not certain. If for example, the number of children for each node was defined to be x, then the complexity would be log_x n. However, when the minimum number of children is 2 (as in Binary Tree) then the maximum height of tree will be logn, and as mentioned in previous answer, Big-O considers the worst case scenario which is a tree with the largest height (log base 2). Therefore, the complexity of B-Tree is O(logn).