# 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

• Big-O 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.  Big-O 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

• Marked as answer by Monday, February 13, 2012 8:47 PM
• Edited by Monday, February 13, 2012 8:48 PM
Monday, February 13, 2012 8:46 PM

### All replies

• Big-O 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.  Big-O 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

• Marked as answer by Monday, February 13, 2012 8:47 PM
• Edited by 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 Big-O notation can be found on wikipedia.

Monday, February 13, 2012 9:59 PM