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
bz, that you would instead define it as O(n^2)
Which is it?
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.