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.
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.O(n^3)
?