Say I solve a problem that has a time complexity linear to the problem set, but on top of that the program used a few 0(1)s to do some function. Would I then have to add all the O(1)s to the O(n) to get the actual Big-Oh?
Asked
Active
Viewed 52 times
0
-
2No you don't.. You define complexity in terms of n here it takes linear time so O(n) – minigeek Feb 07 '17 at 05:09
-
1As long as there is only a constant number of O(1)s they will not change an overall O(n) time. – Henry Feb 07 '17 at 05:13
-
As long as you don't have n of them. – alfC Feb 07 '17 at 06:39
-
@alfC: you probably mean as long as you don't have *more* than (order) n of them. – Yves Daoust Feb 07 '17 at 11:04
-
@YvesDaoust, well, if you have n of them (n of O(1)) (not necessarily "more") then you have O(n). Yes, when I say n, I mean order n. – alfC Feb 07 '17 at 12:23
-
Possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Paul Hankin Feb 07 '17 at 12:47
-
@alfc: I don't think you get it. n of O(1) is harmless, it doesn't deserve an "as long as". – Yves Daoust Feb 07 '17 at 12:51
2 Answers
1
No, the O(1) are not added together as they consume constant space/time irrespective of the inputs to the algorithm or program.
See How to find time complexity of an algorithm for details.
0
You may add the constant terms if you like, but this is of no use. Indeed, O(n) and O(n+27) are equivalent (as well as O(43n-52), O(n/9+1023√n), O(n+log³n), O(√(n²+1))...).
Yves Daoust
- 53,540
- 8
- 41
- 94