What is the amortized cost of a sequence of n insertion in a binary search tree?

Question

How do I calculate the amortized cost of a sequence of n insertions in a binary search tree? The input sequence is random and each insert adds one node.

Answer 1

We want to be able to analyze the time for a single operation and average it over a sequence of operations. We can follow the technique of amortized analysis.

Definition 1

Suppose we have a data structure that supports certain operations. Let T (n) be the worst-case time for performing any sequence of n such operations on this data structure. Then the amortized time per operation is defined as T(n)/n. (source)

Since, you have a Binary search tree, this means that in the worst case scenario you will have a linked-list (all element on the left or all element on the right).

If you have n insertion operation T(n) = 1+2+...n = (n * (n-1)) / 2 = (n^2 - n) / 2.

By the Definition 1 amortized time per operation = (n - 1) / 2. O(n)

Maybe I am interpreting it wrong, so please comment if you think so.

Answer 2

In general, you can expect to generate a roughly-balanced binary tree for a random sequence of insertions, implying an average node height proportional to log(n) (see Wikipedia for explanation). Amortized time = total time / number of operations. The total time is equal to average height * number of elements, or O(n * log(n)). Since the total time is O(n * log(n)), the amortized time is O(log(n)).