Big Oh for (n log n)

int n = 100
for(int i = 0; i < n; i++) //this loop is executed n times, so O(n)
{
    for(int j = n; j > 0; j/=2) //this loop is executed O(log n) times
    {

    }
}

Explanation: The outer for loop should be clear; it is executed n times. Now to the inner loop. In the inner loop, you take n and always divide it by 2. So, you ask yourself: How many times can I divide n by 2?

It turns out that this is O (log n). In fact, the base of log is 2, but in Big-O notation, we remove the base since it only adds factors to our log that we are not interested in.

So, you are executing a loop n times, and within that loop, you are executing another loop log(n) times. So, you have O(n) * O(log n) = O(n log n).