1

I commonly use a site called LeetCode for practice on problems. On a lot of answers in the discuss section of a problem, I noticed that run times like O(N + N) or O(2N) gets changed to O(N). For example:

int[] nums = {1, 2, 3, 4, 5};

for(int i = 0; i < nums.length; i ++) {
    System.out.println(nums[i]);
}

for(int i = 0; i < nums.length; i ++) {
    System.out.println(nums[i]);
}

This becomes O(N), even though it iterates through nums twice. Why is it not O(2N) or O(N + N)?

ShadowRanger
  • 143,180
  • 12
  • 188
  • 271
  • Big O usually only specifies those parameters that have the greatest impact on the computation. So N + N is still a linear relationship. For polynomials it is usually the order of the largest exponent. – WJS Mar 13 '20 at 18:05
  • Big O is an analysis of an algorithm, not an implementation. And often implementation differences can be a constant-time factor faster or slower than another, even for the same algorithms. – Mooing Duck Mar 13 '20 at 18:11

2 Answers2

2

In time complexity, constant coefficients do not play a role. This is because the actual time it takes an algorithm to run depends also on the physical constraints of the machine. This means that if you run your code on a machine which is twice as fast as another, all other conditions being equal, it would run in about half the time with the same input.

But that’s not the same thing when you compare two algorithms with different time complexities. For example, when you compare the running time of an algorithm of O( N ^ 2 ) to an algorithm of O(N), the running time of O( N ^ 2 ) grows so fast with the growth of input size that the O(N) one cannot catch up with it, no matter how big you choose its constant coefficient.

Let’s say your constant coefficient is 1000, instead of just 2, then for input sizes of ( N > 1000 ) the running time of O( N ^ 2 ) algorithm becomes a proportion of ( N * N ) while N would be growing proportional to the input size, while the running time of the O(N) algorithm only remains proportional to ( 1000 * N ).

zmerr
  • 534
  • 3
  • 18
0

Time complexity for O(n+n) reduces to O(2n). Now 2 is a constant. So the time complexity will essentially depend on n.
Hence the time complexity of O(2n) equates to O(n).
Also if there is something like this O(2n + 3) it will still be O(n) as essentially the time will depend on the size of n.
Now suppose there is a code which is O(n^2 + n), it will be O(n^2) as when the value of n increases the effect of n will become less significant compared to effect of n^2.

Pritam Banerjee
  • 17,953
  • 10
  • 93
  • 108
  • I downvoted this because [you posted exactly the same thing in answer to another question](https://stackoverflow.com/a/60675703/12299000). If the same answer applies to two questions then you should vote to close one of them as a duplicate, not post your answer twice. – kaya3 Mar 14 '20 at 15:07