CODEWITHSUNDEEP
algorithmgraphtreebig-ob-tree
CommonSenseCode
CommonSenseCode

Reputation: 25369

What is the big O of counting elements in a B tree

For example if I have a tree which nodes have a structure:

{ type: 'document' } or {type: 'note'}

If I wanted a count of all nodes that have type note what would be count big O for a B tree?

Upvotes: 0

Views: 90

Answers (1)

wohlstad
wohlstad

Reputation: 28084

Traversal of a B-tree can be done in linear time - i.e. O(n). This is because each of the n nodes should be visted once.

You will spend a constant time in each node (checking the type of the node and incrementing a counter, doesn't depend on the size of the tree) - that's O(1).

Therefore the overall complexity should be still linear - O(n).

Upvotes: 2

Related Questions