-3
$\begingroup$

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

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

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.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Would it still be $O(N \times M \times X)$ if they were constants? $\endgroup$ – bogdboa Jun 6 '19 at 17:41
  • $\begingroup$ 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) $ $\endgroup$ – SiluPanda Jun 6 '19 at 17:43

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.