DSA Notes
HubAlgorithm vs Data Structure - Key DifferencesReal-World Applications of DSATime and Space Complexity OverviewWhat is DSA? Data Structures and AlgorithmsWhy Learn Data Structures and AlgorithmsAsymptotic Analysis - Understanding Algorithm GrowthBest, Average, and Worst Case AnalysisBig O Notation - Upper Bound AnalysisBig Omega Notation - Lower Bound AnalysisBig Theta Notation - Tight Bound AnalysisSpace Complexity - Memory AnalysisTime Complexity Examples and AnalysisArray Interview Problems and SolutionsArray Operations - Insert, Delete, SearchArray Rotation TechniquesArray Searching TechniquesArrays - Fundamental Data StructureDynamic Arrays - Flexible SizingMultidimensional Arrays - 2D and BeyondSliding Window Technique for ArraysAnagram Problems - Character RearrangementPalindrome Problems and SolutionsPattern Searching in StringsString Interview Problems CollectionString Matching Algorithms - Pattern SearchingString Operations - Concatenation, Substring, ManipulationString Data Structure - FundamentalsCircular Linked List - Ring StructureDoubly Linked List - Bidirectional TraversalLinked List Interview ProblemsLinked List - Data Structure FundamentalsLinked List Operations - Insert, Delete, ReverseReverse Linked List - Iterative and RecursiveSingly Linked List - Implementation and OperationsBalanced Parentheses - Stack ApplicationInfix, Prefix, Postfix Expressions - Stack ApplicationStack Implementation TechniquesStack Interview Problems and SolutionsStack Data Structure - LIFO PrincipleStack using Arrays - Static ImplementationStack using Linked Lists - Dynamic ImplementationCircular Queue - Efficient Space UsageDeque (Double Ended Queue)Priority Queue - Custom OrderingQueue Applications - Real-World Use CasesQueue Implementation - Array and Linked ListQueue Interview Problems and SolutionsQueue Data Structure - FIFO PrincipleAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap Data StructureHeap OperationsHeap Interview ProblemsMax-HeapMin-Heap Implementation and Use CasesPriority Queue using HeapBellman-Ford AlgorithmBreadth-First Search (BFS) AlgorithmDepth-First Search (DFS) AlgorithmDijkstra\Floyd-Warshall AlgorithmGraph Interview ProblemsGraph Data Structure FundamentalsGraph Representation MethodsKruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete ComparisonTopological SortingUnion-Find (Disjoint Set Union)Separate ChainingCollision HandlingHash FunctionsHashing FundamentalsHashing Interview ProblemsOpen AddressingBubble Sort - Simple Sorting AlgorithmCounting Sort - Non-Comparison SortingHeap Sort - Heap Based SortingInsertion Sort - Build Sorted ArrayMerge Sort - Divide and ConquerQuick Sort - Partition Based SortingRadix Sort - Digit Based SortingSelection Sort - Selection Based SortingSorting Algorithms Comparison - Choosing the Right AlgorithmSorting Algorithms - Fundamentals and ConceptsBinary Search - Efficient SearchingInterpolation Search - Intelligent SearchingLinear Search - Sequential Search AlgorithmSearch Algorithms ComparisonSearching Algorithm Interview ProblemsTernary Search AlgorithmBacktracking with RecursionRecursion Fundamentals - Base Case and RecurrenceRecursion Problems and SolutionsRecursion Tree - Visualizing Function CallsRecursion vs Iteration - Comparing ApproachesTail Recursion - Optimization TechniqueDynamic Programming Interview ProblemsDynamic Programming FundamentalsFibonacci with Dynamic Programming0/1 Knapsack ProblemLongest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain MultiplicationMemoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection ProblemFractional KnapsackGreedy Interview ProblemsGreedy Algorithm FundamentalsHuffman Coding — Data Structures & AlgorithmsJob Sequencing with DeadlinesBacktracking FundamentalsBacktracking Practice ProblemsN-Queens ProblemRat in a MazeSubset GenerationSudoku SolverCodeforces Guide for Competitive ProgrammersCommon Competitive Programming TechniquesContest Strategies for Competitive ProgrammingCompetitive Programming IntroductionFast Input/Output for Competitive ProgrammingLeetCode Guide for Interview PreparationBit Manipulation - Advanced TechniquesBloom Filter - Probabilistic Data StructureComputational Geometry - Algorithms and TechniquesDisjoint Set Union (DSU) - Union FindRandomized Algorithms - Probabilistic ComputingSkip List - Probabilistic Balanced StructureSuffix Array - String IndexingTrie - Prefix Tree for Efficient SearchingAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Complete Big-O reference for all sorting algorithms, searching methods, tree operations, graph algorithms, and common DP problems with notes on when each applies.
How to Read This Guide
This cheatsheet provides the time and space complexity for every important algorithm you will encounter in interviews and courses. The "Notes" column tells you when to choose each algorithm in practice. Bookmark this page — you will reference it constantly.
Sorting Algorithms
| Algorithm | Best Case | Average Case | Worst Case | Space | Stable? | Notes |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Only useful for nearly-sorted data. Educational only. |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Minimizes swaps. Never use in practice. |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Best for small arrays (n < 50). Used inside TimSort. |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Guaranteed O(n log n). External sorting. Linked lists. |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Fastest in practice (cache-friendly). Random pivot avoids worst case. |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | In-place, guaranteed O(n log n). Worse cache than QuickSort. |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes | k = range of values. Only for integers with bounded range. |
| Radix Sort | O(d·(n+k)) | O(d·(n+k)) | O(d·(n+k)) | O(n+k) | Yes | d = digits, k = base. Good for fixed-length integers/strings. |
| Bucket Sort | O(n+k) | O(n+k) | O(n²) | O(n+k) | Yes | Uniform distribution assumed. Good for floating point in [0,1). |
| Tim Sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | Python/Java default. Hybrid merge+insertion. Best real-world sort. |
Practical advice: Use your language's built-in sort (TimSort) for almost everything. Only implement custom sorts when you need specific properties (counting sort for bounded integers, merge sort for external data).
Searching Algorithms
| Algorithm | Best Case | Average Case | Worst Case | Space | Requirement |
|---|---|---|---|---|---|
| Linear Search | O(1) | O(n) | O(n) | O(1) | None |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) | Sorted array |
| Binary Search (recursive) | O(1) | O(log n) | O(log n) | O(log n) | Sorted array |
| Jump Search | O(1) | O(√n) | O(√n) | O(1) | Sorted array |
| Interpolation Search | O(1) | O(log log n) | O(n) | O(1) | Sorted, uniform distribution |
| Exponential Search | O(1) | O(log n) | O(log n) | O(1) | Sorted, unbounded |
| Hash Table Lookup | O(1) | O(1) | O(n) | O(n) | Hash table built |
| BST Search | O(1) | O(log n) | O(n) | O(1) | BST (balanced for guaranteed) |
Tree Operations
| Operation | BST (avg) | BST (worst) | AVL/Red-Black | B-Tree (order m) |
|---|---|---|---|---|
| Search | O(log n) | O(n) | O(log n) | O(log_m n) |
| Insert | O(log n) | O(n) | O(log n) | O(log_m n) |
| Delete | O(log n) | O(n) | O(log n) | O(log_m n) |
| Find Min/Max | O(log n) | O(n) | O(log n) | O(log_m n) |
| In-order Traversal | O(n) | O(n) | O(n) | O(n) |
| Height | O(1)* | O(1)* | O(1)* | O(1)* |
*If stored as attribute; otherwise O(n) to compute.
| Heap Operation | Binary Heap | Fibonacci Heap |
|---|---|---|
| Insert | O(log n) | O(1) amortized |
| Find Min | O(1) | O(1) |
| Extract Min | O(log n) | O(log n) amortized |
| Decrease Key | O(log n) | O(1) amortized |
| Merge | O(n) | O(1) |
| Build from array | O(n) | O(n) |
Graph Algorithms
| Algorithm | Time | Space | Use Case |
|---|---|---|---|
| BFS | O(V + E) | O(V) | Shortest path (unweighted), level-order, bipartite check |
| DFS | O(V + E) | O(V) | Cycle detection, topological sort, connected components, bridges |
| Dijkstra (binary heap) | O((V+E) log V) | O(V) | Single-source shortest path, non-negative weights |
| Dijkstra (Fibonacci heap) | O(V log V + E) | O(V) | Theory optimal, rarely practical |
| Bellman-Ford | O(V·E) | O(V) | Shortest path with negative weights, negative cycle detection |
| Floyd-Warshall | O(V³) | O(V²) | All-pairs shortest path, transitive closure |
| A* | O((V+E) log V) | O(V) | Single pair shortest path with heuristic |
| Kruskal's MST | O(E log E) | O(V) | Minimum spanning tree (sparse graphs) |
| Prim's MST (heap) | O((V+E) log V) | O(V) | Minimum spanning tree (dense graphs) |
| Topological Sort (Kahn) | O(V + E) | O(V) | Task scheduling, dependency resolution |
| Tarjan's SCC | O(V + E) | O(V) | Strongly connected components |
| Kosaraju's SCC | O(V + E) | O(V) | Strongly connected components (simpler) |
| Ford-Fulkerson (Edmonds-Karp) | O(V·E²) | O(V²) | Maximum flow |
| Union-Find (with rank+path) | O(α(n)) ≈ O(1) | O(V) | Dynamic connectivity, Kruskal's |
Dynamic Programming Patterns
| Problem | Time | Space | Category |
|---|---|---|---|
| Fibonacci | O(n) | O(1) | Linear DP |
| Climbing Stairs | O(n) | O(1) | Linear DP |
| House Robber | O(n) | O(1) | Linear DP |
| Longest Common Subsequence | O(m·n) | O(m·n) or O(min(m,n)) | 2D DP |
| Edit Distance | O(m·n) | O(m·n) or O(min(m,n)) | 2D DP |
| 0/1 Knapsack | O(n·W) | O(n·W) or O(W) | 2D DP |
| Longest Increasing Subsequence | O(n log n) | O(n) | Patience sorting |
| Coin Change | O(n·amount) | O(amount) | Unbounded knapsack |
| Matrix Chain Multiplication | O(n³) | O(n²) | Interval DP |
| Longest Palindromic Subsequence | O(n²) | O(n²) or O(n) | Interval DP |
| Word Break | O(n²·m) | O(n) | String DP |
| Subset Sum | O(n·sum) | O(sum) | Knapsack variant |
String Algorithms
| Algorithm | Time | Space | Use Case |
|---|---|---|---|
| Brute Force Matching | O(n·m) | O(1) | Simple pattern search (short patterns) |
| KMP | O(n + m) | O(m) | Pattern matching with failure function |
| Rabin-Karp | O(n + m) avg, O(n·m) worst | O(1) | Multiple pattern search, rolling hash |
| Z-Algorithm | O(n) | O(n) | Pattern matching, string periods |
| Suffix Array (construction) | O(n log n) | O(n) | Substring queries, LCP |
| Trie Insert/Search | O(m) | O(SIGMA·m·n) | Prefix matching, autocomplete |
Data Structure Space Complexities
| Data Structure | Space | Notes |
|---|---|---|
| Array | O(n) | Contiguous memory, cache-friendly |
| Linked List | O(n) | Extra pointer per node (8 bytes on 64-bit) |
| Hash Table | O(n) | ~2x actual entries due to load factor |
| Binary Tree | O(n) | Two pointers per node |
| Heap (array) | O(n) | No extra pointers — just an array |
| Trie | O(SIGMA·n·m) | SIGMA = alphabet size, can be huge |
| Graph (adj list) | O(V + E) | Best for sparse graphs |
| Graph (adj matrix) | O(V²) | Best for dense graphs |
| Segment Tree | O(4n) ≈ O(n) | Range query/update in O(log n) |
| Disjoint Set (Union-Find) | O(n) | Near O(1) per operation with optimizations |
Amortized Complexity Explanations
| Operation | Amortized | Worst Case | Why Amortized? |
|---|---|---|---|
| Dynamic array append | O(1) | O(n) | Doubling happens rarely; cost spreads out |
| Hash table insert | O(1) | O(n) | Rehashing happens every n inserts |
| Splay tree access | O(log n) | O(n) | Frequently accessed nodes move to root |
| Fibonacci heap insert | O(1) | O(1) | Lazy merging defers work |
| Union-Find (find) | O(α(n)) | O(log n) | Path compression flattens over time |
Quick Decision Guide
Need to sort? Use built-in sort (TimSort). It handles everything.
Need fastest lookup? Hash map (O(1) average). Accept O(n) worst case.
Need ordered data + fast ops? Balanced BST (TreeMap/TreeSet). O(log n) everything.
Need min/max repeatedly? Heap. O(1) peek, O(log n) extract.
Need shortest path? BFS (unweighted) or Dijkstra (weighted, non-negative).
Need to detect cycle? DFS with coloring (directed) or Union-Find (undirected).
Need range queries? Prefix sum (static) or Segment Tree (dynamic).
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Complexity Cheatsheet.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, resources, complexity, cheatsheet
Related Data Structures & Algorithms Topics
Continue learning this concept
ResourcesImportant Algorithms SummaryConcise one-paragraph summaries of 30+ essential algorithms grouped by category: sorting, searching, graph, dynamic programming, string, and mathematical algorithms.ResourcesBest Practice Platforms for DSADetailed comparison of LeetCode, Codeforces, HackerRank, GeeksforGeeks, InterviewBit, and CodeChef — features, difficulty levels, and what each is best for.ResourcesRecommended Books for DSAHonest reviews and reading order for the best DSA books: CLRS, The Algorithm Design Manual, Competitive Programming handbook, and Cracking the Coding Interview.Algorithm AnalysisSpace Complexity - Memory AnalysisUnderstand space complexity for analyzing memory usage of algorithms and data structures.Algorithm AnalysisTime Complexity Examples and AnalysisStudy real examples of time complexity analysis for common algorithms and patterns.Interview PreparationDSA Cheatsheet: Quick ReferenceComplete quick-reference cheatsheet covering all data structures with operations and complexities, algorithm complexities, and when-to-use guidelines.