Start learning free

C# · BIG O NOTATION

Time Complexity Guidelines in C#, explained

What constant time means

An operation runs in constant time, written O(1), when the number of steps doesn't depend on the size of the input. Reading one element from an array with ten items and from an array with ten million items takes the same effort.

The "1" doesn't mean the operation takes exactly one step. It means the step count has a fixed upper limit that doesn't grow with n.

Constant-time operations in C#

  • Arithmetic and comparisons on int, long, double and bool: a + b, x % 2 == 0.
  • Reading or writing an array element by index: nums[i] and nums[i] = 5. The runtime goes straight to the slot.
  • Reading an array's Length, a string's Length or a list's Count. The size is already stored.
  • Reading a string character by index: s[3].
  • Reading or writing a list item by index: list[i].
  • Appending to a List<T>: list.Add(x) is constant time on average. Now and then the list has to move its items into a bigger internal array, but that cost is spread over many appends, which is called amortized constant time.
  • Dictionary and set lookups: ContainsKey, TryGetValue and HashSet.Contains are constant time on average.
  • Stack and queue operations: Push, Pop, Enqueue and Dequeue.

A method made only of such operations is O(1):

static int First(int[] nums) {
    return nums[0];
}

static bool IsEven(int x) {
    return x % 2 == 0;
}

Remember that an invalid index, such as nums[0] on an empty array, throws an IndexOutOfRangeException. Constant time says nothing about whether the operation is valid.

Fixed loops are still constant

A loop doesn't automatically make code slower than constant time. What counts is whether the number of passes depends on the input:

static int SumOfFirstThree(int[] nums) {
    int total = 0;
    for (int i = 0; i < 3; i++) {
        total += nums[i];
    }
    return total;
}

This loop always makes three passes, however long the array is, so the method is O(1) (for arrays with at least three elements). Replace the 3 with nums.Length and it becomes O(n).

Guidelines for counting

  1. Straight-line code is constant. Add up the cost of each statement. A fixed number of constant-time statements is still constant.
  2. A loop over the input multiplies. A loop that runs n times around constant-time work is O(n).
  3. Nested loops multiply their counts. Two loops that each run up to n times give O(n²). A loop over n items containing a loop over m items gives O(n·m).
  4. Sequential blocks add. A loop of n passes followed by another of n passes is O(n + n), which is O(n).
  5. Keep the dominant term. O(n² + n) becomes O(n²), and constant factors disappear: O(3n) is O(n).
  6. Check what the calls inside a loop cost. A loop of n passes that calls list.Contains(x) on each pass is O(n²), because Contains itself scans the list. The next lesson looks at the cost of built-in methods.
  7. Halving gives a logarithm. A loop that cuts the remaining work in half on each pass runs about log n times.

Common mistakes

  • Thinking O(1) means fast. A constant-time operation can still be slow if its constant is large. It only means the time doesn't grow with the input.
  • Counting a fixed loop as O(n). Check whether the bound is a literal number or depends on the input.
  • Forgetting hidden loops. Methods such as Contains, IndexOf and Insert on a list do their own looping or shifting.
  • Treating a string append as constant. Strings are immutable, so s += "x" copies the whole string into a new one.

Key takeaways

  • O(1) means the work doesn't grow with the input.
  • Array, string and list indexing, Length, Count, and (on average) dictionary lookups are constant time.
  • A loop with a fixed number of passes is constant; a loop over the input is linear; nested loops multiply.
  • Look inside the calls in a loop: a built-in method may hide its own loop.
Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
Start learning free