locked
O() notation question in documentation RRS feed

  • 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

  • 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
    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

  • 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
    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 Big-O notation can be found on wikipedia.

    Monday, February 13, 2012 9:59 PM