Big O Lab

Learn Big O notation by playing. 12 interactive lessons, 113 C# questions on time and space complexity, an algorithm race and a .NET cheat sheet.

Big O notation explained, with C# examples

Big O Lab teaches time and space complexity through 12 interactive lessons, 113 practice questions built on real C# and .NET code, an algorithm race and a cheat sheet for .NET collections and LINQ. It suits developers preparing for coding interviews and anyone who wants to stop guessing why code gets slow.

Common Big O complexities

  • O(1), constant: array indexing, Dictionary and HashSet lookups on average.
  • O(log n), logarithmic: binary search, SortedDictionary and PriorityQueue operations.
  • O(n), linear: one loop over the input, List.Contains, most LINQ operators.
  • O(n log n), linearithmic: efficient sorting such as Array.Sort, merge sort and OrderBy.
  • O(n²), quadratic: nested loops over the same data, bubble sort, string concatenation in a loop.
  • O(2ⁿ) and O(n!): generating all subsets or permutations, naive recursive Fibonacci.

What you will practice

  • Loops, nested loops and halving loops
  • Recursion, call trees and memoization
  • .NET collections: List, Dictionary, HashSet, SortedDictionary, SortedList, PriorityQueue, immutable and frozen collections
  • LINQ costs, deferred execution and hidden O(n²) traps
  • Strings and StringBuilder
  • Searching, sorting, two pointers, sliding windows and graph traversal
  • Space complexity and amortized cost

Frequently asked questions

What is Big O notation?

Big O notation describes how the running time or memory of an algorithm grows as the input size n grows. It keeps the fastest-growing term and drops constants, so 3n² + 20n + 100 is O(n²).

What is the difference between O(n) and O(log n)?

O(n) work grows in direct proportion to the input, like scanning a list once. O(log n) work grows by one step each time the input doubles, like binary search. For a million items that is about a million steps versus about 20.

How do you find the Big O of code?

Count how many times the innermost statement runs as a function of n. Loops one after another add, nested loops multiply, a loop that halves its range is logarithmic, and a call inside a loop multiplies by that call's own cost. Then keep the largest term and drop constants.

Is Dictionary lookup in C# O(1)?

Yes on average. Dictionary<TKey, TValue> and HashSet<T> use hash tables, so Add, Contains and TryGetValue are O(1) on average and O(n) in the worst case when many keys share a hash code.

What is space complexity?

Space complexity measures the extra memory an algorithm uses as n grows, including the call stack. A recursive function n levels deep uses O(n) stack space, while the same loop written iteratively can use O(1).

What is amortized time complexity?

Amortized cost is the average cost per operation over a long sequence. List<T>.Add sometimes copies the whole array when it grows, but because capacity doubles, the average cost per Add is O(1).

Progress, XP and badges are saved in your browser only.