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.
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.