# Big-O for Immutable Trees

How would you calculate the time and space complexity for a tree algorithm that creates a copy of a tree, but reuses as much of the original tree as possible?

For example,

A
/|\
B C G
/|\
D E F

To change E, we can take a more efficient approach, rather than copying the entire tree:

• Copy E and change the value, call this E'
• Copy C and point it to E' instead of E, call this C'
• Copy A and point it to C', call this A'

The new tree looks like this.

A'
/|\
B C'G
/|\
D E'F

The time taken for updates completely depends which value you want to change and the number of parent nodes between it and the root, rather than the total number of items.

In a worst case scenario, to update a node, you must change h items, where h is the height (maximum depth) of the tree. Is it sane to express the complexity as O(h) (rather than in terms of n)?

If so, what would be a sane way to plot this on a graph that was using the y axis for n and the x axis for Big O? Include a secondary y axis as h? How would you show that h is likely to be far smaller than n?

• You usually have a relation to approximate h from n (often that is the logarithm for trees that are decently balanced) – ratchet freak Sep 4 '15 at 20:11
• What's the rationale behind using that particular approximation? – Dan Prince Sep 4 '15 at 20:16

Is it sane to express the complexity as O(h) (rather than in terms of n)?

Absolutely. It's common and useful to state the big-O of an algorithm in terms of multiple variables.

How would you show that h is likely to be far smaller than n?

This depends on properties of the tree that you have not specified. ratchet freak has correctly stated that for balanced trees h is a logarithm of n, which is also the most useful answer I can give, so I'll attempt to provide the justification for that claim.

Let n be the number of nodes in the tree and a be the arity of the tree (i.e. if every node has at most 2 children, that means a is 2). A tree of height 1 can only have 1 node, and 1 < a. A tree of height 2 can have up to 1+a1 nodes, since the 1 node at height 1 can have up to a children, and 1+a < a2. A tree of height 3 can have up to 1+a1+a2 nodes, since each of the a level 2 nodes can have up to a children each, and 1+a1+a2 < a3. It should be clear that for an a-ary tree of height h, the maximum number of nodes n is between ah-1 and ah.

Justifying this last step rigorously can be quite tedious, but suffice it to say that the previous statement is essentially saying that n=Θ(ah), which is equivalent to saying that h=Θ(logan).

Of course, that holds for perfectly balanced trees. If the tree is not balanced at all then the worst case is h=O(n).