Roadmap › Coding Round Practice (DSA in C#) › Module: Foundations
Lessons in this course (14)
1. Big-O notation
Basic★ Must knowLesson 1 of 14
Big-O describes how time or memory grows as input size n grows (worst case, ignoring constants).
| Big-O | Name | Example |
|---|---|---|
| O(1) | Constant | Array index, dictionary lookup (average) |
| O(log n) | Logarithmic | Binary search, balanced BST |
| O(n) | Linear | Single loop, linear search |
| O(n log n) | Linearithmic | Merge sort, Array.Sort (introsort) |
| O(n²) | Quadratic | Nested loops, bubble sort |
| O(2ⁿ) | Exponential | Naive recursive Fibonacci, all subsets |
| O(n!) | Factorial | All permutations |
C# collection costs: List<T>.Add amortised O(1), Insert(0) O(n), Contains O(n); Dictionary/HashSet add/lookup O(1) average; SortedDictionary O(log n); Array.Sort/List.Sort O(n log n).
Interview tip: always state both time and space complexity, e.g. "O(n) time, O(n) extra space for the dictionary."