Big O for Trees
If a tree is uniform and balanced, we can describe it in terms of
- b, the breadth or branching factor, is the number
of branches per interior node. For a binary tree, b = 2.
- d is the depth, the height of the tree.
d = logb(n)
- n is the number of leaf nodes. n = bd
Note that most of the nodes are on the bottom row of the tree.
If b = 2, half the nodes are on the bottom; if b is higher, an
even greater proportion will be on the bottom.
In general, a tree algorithm will have Big O:
- if one branch of the tree is followed and the others are abandoned,
O(log(n)) because the Big O is proportional to the depth only.
- if all branches of the tree are processed, O(n * log(n))