-2

If an algorithm iterates over a list of numbers two times before returning an answer is the runtime O(2n) or O(n)? Does the runtime of an algorithm always lack a coefficient?

bphi
  • 3,115
  • 3
  • 23
  • 36
  • 1
    This question appears to be off-topic because it is about Computer Science. http://cs.stackexchange.com/ – Fenikso Sep 22 '14 at 17:46
  • Thanks for the answers, I'm aware it's not a great question but I could not find a straight answer anywhere online. – bphi Sep 22 '14 at 17:50

4 Answers4

2

Big-O notation refers to the asymptotic "worst-case" complexity of an algorithm. Any constants are factored out of the analysis. Hence, from a theoretical perspective, O(2n) should always be represented as O(n). However, from the standpoint of practical implementation, if you can cut that down to one iteration over the list of numbers you will see some (small) increase in performance.

wickstopher
  • 981
  • 6
  • 18
0

It may still be slower than an implementation that doesn't iterate twice, but that is still O(n), as the time complexity scales based only on the size of n.

Rowland Shaw
  • 37,700
  • 14
  • 97
  • 166
0

Convention is that you ignore constant coefficients when reporting Big-O time.

So if an algorithm were O(n), O(2n), or O(3n) for example, you would report O(n).

cppprog
  • 804
  • 3
  • 12
  • 22
0

Your suspicion is correct. You leave off the coefficient. See http://en.wikipedia.org/wiki/Big_O_notation.

From the example,

Now one may apply the second rule: $6x^4$ is a product of 6 and $x^4$ in which the first factor does not depend on x. Omitting this factor results in the simplified form $x^4$.

rajah9
  • 11,645
  • 5
  • 44
  • 57