N log(N) or N clarification

Question

Will performing a O(log N) algorithm N times give O(N log(N))? Or is it O(N)?

e.g. Inserting N elements into a self-balancing tree.

int i = 0;
while (i++ < N) {
    insert(itemsToInsert[i]);
}

Answer 1

It's definitely O(N log(N)). It COULD also be O(N), if you could show that the sequence of calls, as a total, grows slow enough (because while SOME calls are O(log N), enough others are fast enough, say O(1), to bring the total down).

Remember: O(f) means the algorithm is no SLOWER than f, but it can be faster (even if just in certain cases).

Answer 2

N times O(log(N)) leads to O(N log(N)).

Answer 3

Big-O notation notates the asymptotic behavior of the algorithm. The cost of each additional step is O(log N); we know that for an O(N) algorithm, the cost of each additional step is O(1) and asymptotically the cost function bound is a straight line.

Therefore O(N) is too low of a bound; O(N log N) seems about right.

Answer 4

Yes and no.

Calculus really helps here. The first iteration is complexity log(1), the second iteration is log(2), &ct until the Nth iteration which is log(N). Rather than thinking of the problem as a multiplication, think of it as an integral...

This happens to come out as O(N log(N)), but that is kind of a coincidence.