, Table of Contents
1. Foundations & Complexity
2. Mathematics & Number Theory
3. Bit Manipulation
4. DSA Coursebook
5. Searching
6. Sorting
7. Two Pointers
8. Sliding Window
9. Kadane Algorithm
10. Prefix Sum
11. Frequency Counting
12. Monotonic Stack
,Foundations & Complexity
, ■ Foundations Refresher – Complexity & Notations
1. Big-O, Big-Ω, Big-Θ Notation
■ Big-O (Upper Bound)
• Definition: Describes the worst-case growth rate of an algorithm.
• Meaning: Algorithm won’t take more than this much time for large input.
• Example: Linear Search → O(n).
■ Big-Ω (Lower Bound)
• Definition: Describes the best-case growth rate.
• Meaning: Algorithm will take at least this much time.
• Example: Linear Search best case → Ω(1).
■ Big-Θ (Tight Bound)
• Definition: When algorithm’s upper and lower bounds are same.
• Meaning: Algorithm always runs in this complexity.
• Example: Linear Search average case → Θ(n).
■ Analogy:
• O → Worst-case guarantee (‘at most this slow’)
• Ω → Best-case guarantee (‘at least this fast’)
• Θ → Exact growth (‘this is how it scales overall’)
2. Common Complexity Classes
● O(1): Constant Time → Array access, Hash lookup.
● O(log n): Logarithmic → Binary search.
● O(n): Linear → Traversals, Linear search.
● O(n log n): Linearithmic → Merge sort, Heap sort.
● O(n²): Quadratic → Bubble sort, Nested loops.
● O(2■): Exponential → Subset generation, brute force.
● O(n!): Factorial → Travelling Salesman brute force.
3. Complexity Comparison Tables
1. Foundations & Complexity
2. Mathematics & Number Theory
3. Bit Manipulation
4. DSA Coursebook
5. Searching
6. Sorting
7. Two Pointers
8. Sliding Window
9. Kadane Algorithm
10. Prefix Sum
11. Frequency Counting
12. Monotonic Stack
,Foundations & Complexity
, ■ Foundations Refresher – Complexity & Notations
1. Big-O, Big-Ω, Big-Θ Notation
■ Big-O (Upper Bound)
• Definition: Describes the worst-case growth rate of an algorithm.
• Meaning: Algorithm won’t take more than this much time for large input.
• Example: Linear Search → O(n).
■ Big-Ω (Lower Bound)
• Definition: Describes the best-case growth rate.
• Meaning: Algorithm will take at least this much time.
• Example: Linear Search best case → Ω(1).
■ Big-Θ (Tight Bound)
• Definition: When algorithm’s upper and lower bounds are same.
• Meaning: Algorithm always runs in this complexity.
• Example: Linear Search average case → Θ(n).
■ Analogy:
• O → Worst-case guarantee (‘at most this slow’)
• Ω → Best-case guarantee (‘at least this fast’)
• Θ → Exact growth (‘this is how it scales overall’)
2. Common Complexity Classes
● O(1): Constant Time → Array access, Hash lookup.
● O(log n): Logarithmic → Binary search.
● O(n): Linear → Traversals, Linear search.
● O(n log n): Linearithmic → Merge sort, Heap sort.
● O(n²): Quadratic → Bubble sort, Nested loops.
● O(2■): Exponential → Subset generation, brute force.
● O(n!): Factorial → Travelling Salesman brute force.
3. Complexity Comparison Tables
