Algorithms

Sorting, searching, complexity analysis

Practice →

Algorithms are step-by-step procedures for solving computational problems. Understanding algorithm complexity (Big-O notation), sorting methods, searching techniques, and paradigm approaches like dynamic programming and greedy algorithms is essential for technical interviews and competitive programming. This module covers fundamental algorithmic concepts with their time and space complexities.

Complexity / Key Facts

Time Complexity: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2 ) < O(n!)\text{Time Complexity: O(1) < O(log n) < O(n) < O(n log n) < O(n\textasciicircum{}2) < O(n\textasciicircum{}3) < O(2 ) < O(n!)}
Space Complexity: Memory used excluding input, often O(1), O(log n), or O(n)\text{Space Complexity: Memory used excluding input, often O(1), O(log n), or O(n)}
Binary Search: T(n) = T(n/2) + O(1) -> O(log n) time, O(1) space\text{Binary Search: T(n) = T(n/2) + O(1) -> O(log n) time, O(1) space}
Merge Sort: T(n) = 2T(n/2) + O(n) -> O(n log n) time, O(n) space\text{Merge Sort: T(n) = 2T(n/2) + O(n) -> O(n log n) time, O(n) space}
Quick Sort: Average O(n log n), Worst O(n^2), Space O(log n)\text{Quick Sort: Average O(n log n), Worst O(n\textasciicircum{}2), Space O(log n)}
Bubble/Selection/Insertion Sort: O(n^2) time, O(1) space\text{Bubble/Selection/Insertion Sort: O(n\textasciicircum{}2) time, O(1) space}
BFS/DFS: O(V + E) time where V=vertices, E=edges\text{BFS/DFS: O(V + E) time where V=vertices, E=edges}
Dynamic Programming: Optimal substructure + Overlapping subproblems -> Memoization/Tabulation\text{Dynamic Programming: Optimal substructure + Overlapping subproblems -> Memoization/Tabulation}

Key Concepts

Big-O Notation

Big-O describes the upper bound of algorithm growth rate as input size n approaches infinity. O(1) is constant time (best), O(log n) is logarithmic (binary search), O(n) is linear (single loop), O(n log n) is linearithmic (efficient sorts), O(n^2) is quadratic (nested loops), and O(2 ) is exponential (brute force). When analyzing, drop constants and lower-order terms: O(2n + 3) becomes O(n). Space complexity tracks auxiliary memory used.

Sorting Algorithms

Comparison-based sorts: Bubble Sort (adjacent swaps), Selection Sort (find minimum), Insertion Sort (build sorted portion) - all O(n^2). Efficient sorts: Merge Sort (divide and conquer, stable, O(n log n)), Quick Sort (pivot partitioning, average O(n log n), unstable). Non-comparison: Counting Sort O(n+k), Radix Sort O(dx(n+b)). Stability matters when equal elements must maintain relative order. Merge Sort is always O(n log n) but uses O(n) space; Quick Sort is in-place but O(n^2) worst case.

Searching Algorithms

Linear Search checks each element sequentially - O(n) time, works on unsorted data. Binary Search requires sorted array, repeatedly halves the search space by comparing with middle element - O(log n) time, O(1) space. Binary Search can find first/last occurrence by adjusting bounds. Interpolation Search estimates position for uniformly distributed data - O(log log n) average, O(n) worst. Ternary Search divides into three parts for unimodal functions.

Graph Traversal: BFS and DFS

Breadth-First Search (BFS) explores level by level using a queue, finding shortest path in unweighted graphs. Depth-First Search (DFS) explores as deep as possible using recursion/stack, good for cycle detection and topological sort. Both visit each vertex and edge once: O(V + E) time, O(V) space for visited set. BFS uses queue; DFS uses call stack (implicit) or explicit stack. DFS variants: preorder, inorder, postorder for trees.

Dynamic Programming

DP solves problems by breaking into overlapping subproblems and storing results to avoid recomputation. Requirements: Optimal substructure (optimal solution contains optimal subsolutions) and overlapping subproblems (same subproblems solved multiple times). Two approaches: Top-down (memoization - recursive with cache) and Bottom-up (tabulation - iterative filling table). Classic examples: Fibonacci, Longest Common Subsequence, 0/1 Knapsack, Matrix Chain Multiplication. Trade space for time.

Greedy Algorithms

Greedy makes locally optimal choice at each step hoping for global optimum. Works when problem has greedy choice property (local optimal leads to global optimal) and optimal substructure. Examples: Activity Selection, Huffman Coding, Dijkstra's shortest path (non-negative weights), Kruskal's/Prim's MST. Unlike DP, greedy doesn't reconsider choices. Not always optimal - verify with proof or counterexample. Often simpler and faster than DP when applicable.

Tips

  • Always state both time and space complexity in answers -- interviewers expect both.
  • For sorting questions, mention stability and whether the algorithm is in-place (uses O(1) extra space).
  • Binary search can be tricky with boundary conditions -- practice finding first/last occurrence and floor/ceiling variants.
  • Recognize DP problems by looking for 'optimal' or 'maximum/minimum' with overlapping subproblems -- if recursion solves same subproblem multiple times, use memoization.
  • When comparing O(n^2) vs O(n log n), remember that for n=10 , n^2 = 10^1^2 operations (too slow) while n log n ~= 2x10 (acceptable).
  • For graph problems, BFS gives shortest path in unweighted graphs; Dijkstra for weighted with non-negative edges; Bellman-Ford for weighted with possible negative edges.

Practice with questions

Real placement-style technical questions.

Start Exercise →