3

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

Tony Tannous
  • 14,154
  • 10
  • 50
  • 86
Derp
  • 143
  • 1
  • 2
  • 11

2 Answers2

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.

Carlos
  • 5,991
  • 6
  • 43
  • 82
  • 1
    So, it needs to be some form of division, we cannot reduce it by a constant size each time? – Derp Nov 29 '17 at 22:27
  • What do you mean by "some form of division"? – juanpa.arrivillaga Nov 29 '17 at 22:29
  • Reducing it by a constant would give you a linear complexity. Think about it, if you had to walk twice as far as some reference, you'd need twice as many steps. If you could jump some proportion of the way there, you'd need just that inverse proportion more if you increased it. – Carlos Nov 29 '17 at 22:29
  • @Carlos So, if I were to only reduce the problem linearly (i.e. remove one item each iteration), the problem will become n^2 rather than n log n, as in algorithmic analysis we drop constants, so this would still technically be n, even if it were O(n-10) (or something). I've got it now. Thanks! – Derp Nov 29 '17 at 22:33
1

The code shown is O(n^2)

Outer loop determines number of iterations for the inner loop. N + N-1 + N-2 + N-3 + ... + 1 = O(n^2)

To get a complexity of log(n), at each iteration you need to get rid of cn elements. Where 0<c<1

Tony Tannous
  • 14,154
  • 10
  • 50
  • 86