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