Insert N elements into an empty binary search tree

Each element is O (n), and there are n elements. Even though the O (n) for each item is "increment as it appears" n, you still end up with 0 + 1 + 2 + 3 ... (n-1) which is n (n-1) / 2 = O (n ^ 2).

In other words, let's say we add 10, 20, 30, 40:

Step 1: empty tree, insert 10:

10

      

        
        
        
      

    

Step 2: Compare 20 to 10 larger, so the tree will be:

10
  \
   20

      

        
        
        
      

    

Step 3: Compare 30 to 10 bigger, so go to node at 20. compare 30 to 20; larger, so the tree will be:

10
  \
   20
     \
      30

      

        
        
        
      

    

Step 4: Compare 40 to 10 bigger, so go to node at 20. compare 40 to 20; bigger, so go to node at 30. compare 40 to 30; larger, so the tree will be:

10
  \
   20
     \
      30
        \
         40

      

        
        
        
      

    

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

Of course, this is only the case if you are inserting in sort order (small to large or large to small). The insertion into the order that occurs to balance the tree will be significantly cheaper.