Total time complexity when each step takes O(log n) operations

Question

Consider a tree where the cost of an insertion is in O(log n). Say you start from an empty tree and add N elements iteratively. We want to know the total time complexity. I did this:

nb of operations in iteration i = log i
nb of operations in all iterations from 1 to N = log 1 + log 2 + ... + log N = log( N! ) 
total complexity =  O(N!) ~ O(N log N)

(cf the Stirling approximation http://en.wikipedia.org/wiki/Stirling%27s_approximation )

Is this correct?

Answer 1

Yes, it's nearly correct.

A small correction: in the ith step, the number of operations is not log i, as most of the time that's an irrational number, it's O(log i). So for a mathematically tight proof you have to work a bit harder, but in short, what you wrote is the essence of the proof.