1

What time complexity would you classify the following as having?

int n = 100;
for(int x = 0; x < n; x++)
    for(int y = 0; y < n; y++)
        for(int z = 0; z < n; z++)
            DoWork(x,y,z);

I don't think anyone would argue that it's O(n^3)

Now consider a scenario where the bounds for each dimension are provided as 3 seperate inputs

int bx = 10, by = 1000, bz = 1000
for(int x = 0; x < bx; x++)
    for(int y = 0; y < by; y++)
        for(int z = 0; z < bz; z++)
            DoWork(x,y,z);

How would you describe the complexity of the above? I would have intuitively described this as still being O(n^3) as you still need to iterate in all 3 dimensions.

A friend suggested that the magnitude of the input comes into play and since bx is several orders of magnitude less than by or bz, that you would instead define it as O(n^2)

Which is it?

Edit

Just to provide a little more context as people have been voting to close the question.

This came out of a discussion around the AdventOfCode 2018 - Puzzle 6 (https://adventofcode.com/2018/day/6)

The "bounds" of this puzzle, were a 50 line input file where each input defined a point. So every competitor was working on a solution that was bounded by

  • number of inputs: 50 --constant
  • n = max-x coord: different per competitor - unique input values we generated for each user
  • m = max-y coord: different per competitor - unique input values we generated for each user

I think based on the feedback below, that makes the best case O(n*m) as you'd just ignore the constant 50 input values.

  • 1
    Adding constant values for n, bx, by, and bz confuses the question. It's why your friend has come up with the wrong answer. You could describe this as O(n^3) if all three dimensions are always roughly the same size. Otherwise see Sahil's answer. – JimmyJames Dec 7 '18 at 18:20
  • 1
    you could also call it O(n * m * o) – Erik Eidt Dec 7 '18 at 18:27
  • 2
    Possible duplicate of What is O(...) and how do I calculate it? – gnat Dec 7 '18 at 18:37
  • 1
    In your second example, there is no variable n, so calling it O(n^3) or O(n^2) makes simply no sense. If you define bx, by and bz in terms of some n, your question would become answerable, and the answer will depend on that missing definition. – Doc Brown Dec 8 '18 at 11:47
  • 1
    This sentence ... I don't think anyone would argue that it's O(n^3) ... seems ambiguous to me. Does OP mean that no-one would argue for or or that no-one would argue against the complexity of this algorithm belonging to O(n^3) ? – High Performance Mark Dec 9 '18 at 15:20
7

Personally I would put it as O(bx*by*bz). The reason being I assume that the parameters can all change arbitrarily to one another, for example you could get the following input: bx=30000, by=30, bz=40. See how the big-Oh is now dependent on the bx instead due to it being many orders of magnitude higher? However, if those values are always constant say always bx = 10, by = 1000, bz = 1000 then it would be O(1).

| improve this answer | |
  • I don't recognise O(bx*by*bz) as a standard expression of any class of computational complexity. Does OP perhaps mean O(n^3) ? If so, how does OP then assign the same algorithm to class O(1) when the size of the number inside the () changes ? – High Performance Mark Dec 10 '18 at 8:02
  • Well, there is no concept of n being used. It doesn't say that bx,by, and bz all depend on the same variable n. Meaning bx,by and bz can all vary on their own. Saying that its O(n^3) would be misleading. It can be O(1) if all of bx, by and bz are constant and don't depend on any external factors. Since in all cases it would run in a constant amount of time. Consider the following bx approx = by approx = bz only then would it be O(bx^3), but for the general case its more correct to say O(bx*by*bz), unless of course they are each always constant in which case its O(1) as mentioned before. – Sahil Tara Dec 10 '18 at 11:32
3

The first thing you need to study detail about asymptotic analysis and amortized analysis.

If we consider Asymptotic analysis for your scenario with bx = 10, by = 1000, bz = 1000 as your friend suggested if you consider input set by and bz then relatively bx is having a tiny value which can be considered as constant However in your case all these values are itself constant and it's running time can be considered as O(1).

While calculating asymptotic upper bound Big-O 'O' we ignore the constants.

However, if you just use values like: bx = 1000000000, by = 100000000000, bz = 100000000000 where the input size of bx also relatively higher hence by definition of big-o

That is, f(x) = O(g(x)) if and only if there exists a positive real number c and a real number x' such that
f(x) <= c g(x) for all x > x'

you can state the complexity to O(bx*by*bz).

To summarize in the first case you used the same value n to compute all loops but in another case, you used three different input size hence your complexity will always be O(bx*by*bz) and if any one or more value of bx, by or bz is constant then you can omit it.

| improve this answer | |
0

There's a big, important detail missing in the other answers to the question here. This:

int n = 100;
for(int x = 0; x < n; x++)
    for(int y = 0; y < n; y++)
        for(int z = 0; z < n; z++)
            DoWork(x,y,z);

is not a cubic-time O(n^3) algorithm. Its runtime depends on the value of the single input n, not the size of the input called n. This program runs in pseudo-polynomial time because it is polynomial in the numeric value of its input but it is actually exponential in the size of its input (which is log_2(n), the number of bits needed to represent it).


The other answers are therefore correct that your algorithm runs in O(bx * by * bz), but your statement that

I would have intuitively described this as still being O(n^3) as you still need to iterate in all 3 dimensions.

is wrong. Big-O counts the number of operations, not the depth of a loop nest.

| improve this answer | |
  • This answer is correct, but quite misleading. It would be correct and accurate to state for that example that “the number of DoWork invocations is in O(n^3)” (assuming n is an external input and not a constant). Whether the value of a number or the bit-string length of a number is used depends on context, and on the abstract machine we are using. For practical problems this is usually not a Turing machine! It is typically fine to simplify so that arithmetic operations all take constant time, and this simplification goes without saying in software engineering. – amon Dec 9 '18 at 18:13
  • 1
    @amon - It is absolutely not misleading. There was a clear misunderstanding in the statement of the question: why else would anyone assume that the latter loop takes O(n^3) time? If such distinctions didn't matter, then the trial division algorithm for primality testing would take linear time and therefore be "very efficient". – Alex Reinking Dec 9 '18 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.