# BigO time complexity of 3 nested for loops

I'm debating with a friend whether a particular function I wrote is $$O(N^3)$$ or $$O(N \times M \times X)$$

I believe it is the latter since all 3 variables differ in size. $$N = 100, M = 50, X = 10000$$

for i in range(len(N)):
for j in range(len(M)):
for p in range(len(X)):
if statement:
count += 1
list.append(count)


The outer loop executes $$N$$ times, the inner loop executes $$M$$ times, and the most inner loop executes $$X$$. Hence giving $$N \times M \times X$$. His theory is that because $$X$$ is so much greater than the other two variables it makes it $$O(N^3)$$

• What is the variable $n$? How much time does the append function take? Are $N$, $M$, and $X$ constants or variables? – ryan Jun 6 '19 at 17:14
• @ryan Assume append is $O(1)$ and $N, M$ and $X$ are all variables. – bogdboa Jun 6 '19 at 17:17
• @ryan Sorry that was a typo, $n$ should actually be $N$ – bogdboa Jun 6 '19 at 17:19

Obviously you can't say it's $$O(N^3)$$ because X might grow a lot faster than N. But you can't even say it's O (N x M x X), because you don't know how often the "list.append(count)" is executed and what the time complexity of that operation is.
As you have mentioned that $$N, M, X$$ are variables, the time complexity would be $$O(N*M*X)$$.
A possible counter argument for the complexity not equal to $$O(N^3)$$ is, what if the rate of increase of $$X$$ is greater than rate of increase of $$N$$ ?
• Would it still be $O(N \times M \times X)$ if they were constants? – bogdboa Jun 6 '19 at 17:41
• If they were constants, you can just say that, the program takes constant time. If only N is a variable, you can say that program takes $M * X * O(N)$ time, which is equivalent to $O(N)$ – SiluPanda Jun 6 '19 at 17:43