insert N items into an empty binary search tree

Question

Why is the worst case big-O for inserting N items into an empty binary search tree n^2? there are no balance checks.

Answer 1

In the worst case, your BST is a list, and insertion of N items to the end of an empty is is O(n^2).

Answer 2

Each item is O(n), and there are n items. Even though the O(n) per item is an "increasing as it goes" n, you still get 0 + 1 + 2 + 3 ... (n-1) which is n(n-1)/2 = O(n^2).

In other words, suppose we're adding 10, 20, 30, 40:

Step 1: empty tree, insert 10:

10

Step 2: compare 20 with 10; bigger, therefore tree becomes:

10
  \
   20

Step 3: compare 30 with 10; bigger, so move down to node with 20. compare 30 with 20; bigger, therefore tree becomes:

10
  \
   20
     \
      30

Step 4: compare 40 with 10; bigger, so move down to node with 20. compare 40 with 20; bigger, so move down to node with 30. compare 40 with 30; bigger, therefore tree becomes:

10
  \
   20
     \
      30
        \
         40

Notice how we get one more comparison each time - so the first element takes 0 comparisons, the second takes 1, the third takes 2 etc - summing to n(n-1).

Of course, this is only the case if you insert in sort order (either small to big or big to small). Inserting in an order which happens to balance the tree will be significantly cheaper.