Algorithmic complexity O(n*log(n))- Do we need to divide by 2?

Question

In many definitions of O(n log(n)), I typically see as a requirement that the subproblem must be a division of the original problem size by two. However, in particular, I have seen that O(log(n)) need only be a problem of reducing size.

Do we necessarily need to divide the problem into halves to get a problem of nlog(n)?

Or could it be merely a reductive problem? Like so:

for (i = 0; i < A.length(); i++)
{
    for (j = i; j < A.length(); j++)
    {
        //do something
    }
}

Would something like this also be categorized as n(log(n))? Or is it closer to O(n^2)?

Answer 1

Dividing by any other constant would also give you log(n) complexity. That's because you can convert log bases, and the constant drops out when you are interested in Big-O.

http://www.purplemath.com/modules/logrules5.htm

You'll note the denominator is a constant.