Taken from here Marcelo Cantos has replied:
O((n/2 + 1)*(n/2)) = O(n2/4 + n/2) = O(n2/4) = O(n2)
Up to
O(n2/4) = O(n2)
I can understand, but why is the dividing by 4 ignored (or the multiplying by 1/4)?
Asked
Active
Viewed 107 times
-1
-
Because 4 is much less than N. – fasked Jan 12 '14 at 14:00
-
2This question appears to be off-topic because it is about computer science, not programming. Use the CS stackexchange site. – Wooble Jan 12 '14 at 14:01
-
In "big O" computations you ignore all constant multipliers and only concern yourself with the power of N. (Yes, it can be kind of silly in some cases but makes sense when N is very large.) – Hot Licks Jan 12 '14 at 14:01
1 Answers
4
Constant multipliers are ignored when dealing with complexity. Whether a step in an algorithm is 2, 4, or 1000 times as long as a step in another algorithm is irrelevant when all we care about is the number of steps involved.
Ignacio Vazquez-Abrams
- 776,304
- 153
- 1,341
- 1,358
-
+1, and the reason why we ignore the constants and multipliers is, because they are unimportant compared to the exponent. – Boris Stitnicky Jan 12 '14 at 14:14