Why The Plain Column Jumps

The 15-122 notes insert $n$ entries into a tree and look them all up, timing AVL trees against plain binary search trees that never rebalance. Each row is 100 repetitions, in seconds:

n	AVL	plain BST
$2^{11}$	0.620	3.094
$2^{12}$	1.373	7.745
$2^{13}$	2.980	20.443
$2^{14}$	6.445	27.689
$2^{15}$	13.785	48.242

The AVL column roughly doubles each row. The plain column multiplies by 2.5, then 2.6, then 1.35, then 1.7. The keys were the integers counted upward and converted to strings, compared lexicographically, so the order is "0" < "1" < "10" < "12" < "2" and so on.

What explains the plain column's uneven growth?

The plain tree spends most of its time in allocation, and allocation cost is not smooth in n.

Its cost is driven by the tree's height, which depends on insertion order, and this key order is haphazard without being random, so each doubling of n reshapes the tree by an unpredictable amount.

The plain tree degenerates into a linked list on these keys, so its cost is quadratic and the ratios are just measurement noise.

The plain tree does more comparisons per node because it has no stored height field to short-circuit the descent.