CODEWITHSUNDEEP
time-complexityb-tree
aol
aol

Reputation: 377

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.

Upvotes: 0

Views: 4671

Answers (3)

Hadi GhahremanNezhad
Hadi GhahremanNezhad

Reputation: 2445

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).

Upvotes: 3

Pubudu Mahesh Meththananda
Pubudu Mahesh Meththananda

Reputation: 387

yes, it is not a binary tree. But if we perform binary serach algoritm inside a node (for the kyes inside a node) time complexity can be considered as O(logn).

let's consider,

degree of the B-tree (maximum number of children per node) ≤ m. total number of nodes in the node : n

if the case is like above,

height of the tree is 

O(logmn)   ----------(1)
since number of children can be changed per node, will have to do a logarithmic search per node order 
(lgm)   ----------(2)

so total complexity for search in binary tree is

O(logmn) . O(lgm)   ----------(3)

according to the logarithmic operation ,

{logba = logca / logcb}

applying the above operation to (3)

O(logmn) . O(lgm) = O(lgn/lgm) . O(lgm)
                  = O(lgn)

so B tree time complexity for search operation is O(lgn)

Upvotes: 2

Scott Hunter
Scott Hunter

Reputation: 49803

Big-O is a measure of worst case complexity; since B-tree nodes are not required to have more than 2 children, the worst case will be that no node has more than 2 children.

Upvotes: 0

Related Questions