From charlesreid1

Measuring tree class operations

This page covers performance tests of tree class operations and verification of their big-O performance.

Linked binary tree

The process of building the linked binary tree class in Java was:

The timing script was used to perform verification that the amortized cost of the add and remove operations were as expected.

Note that these measurements were run on full binary trees, so consider the inputs biased.

Adding nodes

TreeTiming Add.png

Removing nodes

TreeTiming Remove.png

Traversing nodes

TreeTiming Traverse.png

Note that these results are not saying the breadth-first traversal takes O(1) time, they are showing the per-operation cost of traversing a single node (like adding or removing a single node). This should remain O(1) cost if the overall operation of traversing the tree is to scale like O(N). If the cost of traversal scales like O(N), there is a leaky algorithm implementation and it will scale like O(N^2) when the rubber meets the road.