Answered by:
O() notation question in documentation
Question

In the C# reference, many operations are said to have O(1) complexity. I may just be forgetting what O(1) means, but does that mean O(1) operations take only a single operation to complete? Alternatively, is this shorthand for O(constant)? I try to document my code as verbosely as possible and follow standard documentation format, so I want to label my methods accordingly.
My question stated more practically:
Are the methods
void SetOne(int val1) { field1 = val1; }
and
void SetTwo(int val2, int val3) { field2 = val2; field3 = val3; }
both O(1), or is the second one O(2) (since there are two operations to compute)?
Monday, February 13, 2012 8:38 PM
Answers

BigO notation does not have any relation to the number of operations. A routine can be O(1) and take millions of individual operations to complete.
O(1) means that the runtime complexity does not depend on how many objects are in the underlying collection. BigO notation is used when dealing with many objects, not a single object. (That being said, both of your operations would be considered O(1), but this isn't really a useful thing as you're not dealing with collections of objects...).
For example, take HashSet<T>.Contains  this is an O(1) operation because the speed of the operation doesn't change as you add many items to the collection. List<T>.Contains, on the other hand, is O(n)  if you double the length of the list, it's going to normally take twice as long to run.
Reed Copsey, Jr.  http://reedcopsey.com
If a post answers your question, please click "Mark As Answer" on that post and "Mark as Helpful".
 Marked as answer by hoylemd Monday, February 13, 2012 8:47 PM
 Edited by Reed Copsey, JrMVP Monday, February 13, 2012 8:48 PM
Monday, February 13, 2012 8:46 PM
All replies

BigO notation does not have any relation to the number of operations. A routine can be O(1) and take millions of individual operations to complete.
O(1) means that the runtime complexity does not depend on how many objects are in the underlying collection. BigO notation is used when dealing with many objects, not a single object. (That being said, both of your operations would be considered O(1), but this isn't really a useful thing as you're not dealing with collections of objects...).
For example, take HashSet<T>.Contains  this is an O(1) operation because the speed of the operation doesn't change as you add many items to the collection. List<T>.Contains, on the other hand, is O(n)  if you double the length of the list, it's going to normally take twice as long to run.
Reed Copsey, Jr.  http://reedcopsey.com
If a post answers your question, please click "Mark As Answer" on that post and "Mark as Helpful".
 Marked as answer by hoylemd Monday, February 13, 2012 8:47 PM
 Edited by Reed Copsey, JrMVP Monday, February 13, 2012 8:48 PM
Monday, February 13, 2012 8:46 PM 
Thanks! Exactly the type of answer I was hoping for.
Hoylemd http://www.michaelhoyle.com
Monday, February 13, 2012 8:48 PM 
Some further reading material on the BigO notation can be found on wikipedia.
Monday, February 13, 2012 9:59 PM