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

Issue

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?

Solution

Traversal of a B-tree can be done in linear complexity - 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).

Answered By - wohlstad

Answer Checked By - Candace Johnson (PHPFixing Volunteer)