Starting with an empty tree, what is the complexity of inserting into Red Black Tree in big-O notation?

Question

If I have 10 elements and starting with an empty tree, What is the complexity of inserting 10 elements into Red Black in big-O notation?

Is it going to be more than O(log 10) because each time it inserts an element, it has to search for appropriate location for the element and performs a series of rotations between ancestor nodes and child nodes. So if I have N element and inserting N times into Red Black Tree, wouldn't that make it O(n log n)?

Thanks for any help.

Answer 1

The time-complexity of inserting a single element into an RB-tree is O(log n) where n is the current size of the tree.

The time-complexity of inserting n elements into an empty RB-tree is, therefore, O(n log n).

The time-complexity of inserting 10 elements into an empty RB-tree is constant, or O(1). Because the tree starts empty, and because the number of elements being inserted is fixed, there are no variable elements here.

Answer 2

You never use big-O with a constant (except 1) because O(10) means exactly the same as O(1) or O(128291), so by convention you always use O(1)!

So, let's see what's the big-O of inserting K items into an initially empty RB-tree. The first insertion is a constant time so call it O(1); and inserting when there are X items the X+1st is O(X) (even if you have to rotate each step down, it's still worst-case proportional to X, so, O(X)).

So we want the summation of log(X) for X from 2 to N (plus a costant), which happens to be equal to the log of the factorial of N. Per Stirling's approx, that's about N log(N) - N, which in big-O terms boils down to N log(N) again.

Answer 3

What @Justice and @Alex are really getting at is that a O(f(N)) complexity measure talks about the limiting behavior (e.g. time to run, number of comparisons, whatever) as N tends to infinity.

They are saying that if you substitute a particular value for N, the O terminology is no longer meaningful.

There is another point that they didn't make. That is that you cannot use a statement in O(...) notation to tell you what happens when N is small. Because, by definition it tells you nothing about what happens in that case.

For example the cost function F(N) = 1,000,000 * N + N**2 is O(N**2), but the first term dominates for values of N less than 1,000. If you try to use the O(...) measure as an estimator, you got totally the wrong answer.