Algorithms
Sorting, searching, complexity analysis
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.
Key formulas and rules
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.
Worked examples
Example 1
What is the time complexity of the following nested loop?
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
sum += arr[i][j];
Step 1: Analyze outer loop — runs n times (i from 0 to n-1)
Step 2: For each outer iteration, inner loop runs n times (j from 0 to n-1)
Step 3: Total operations = n x n = n^2
Step 4: Each operation is O(1) constant time
Step 5: Therefore, time complexity is O(n^2) or quadratic
Note: This is independent of the input array values, only depends on size n.
Example 2
Apply binary search to find 23 in sorted array [2, 5, 8, 12, 16, 23, 38, 45, 56].
Step 1: Initial range: low=0, high=8, mid=(0+8)/2=4, arr[4]=16
Step 2: 23 > 16, so search right half: low=5, high=8, mid=(5+8)/2=6, arr[6]=38
Step 3: 23 < 38, so search left half: low=5, high=5, mid=(5+5)/2=5, arr[5]=23
Step 4: Found at index 5!
Step 5: Total comparisons: 3 (log 9 ~= 3.17, rounded up)
Time complexity: O(log n) = O(log 9) ~= 3 steps.
Example 3
Solve the 0/1 Knapsack problem using DP: Capacity=5, Items=[(weight:2, value:3), (weight:3, value:4), (weight:4, value:5)]
Step 1: Create DP table of size (items+1) x (capacity+1) = 4x6
Step 2: Initialize first row and column to 0 (no items or no capacity = 0 value)
Step 3: For each item i and capacity w:
- If weight[i] > w: dp[i][w] = dp[i-1][w] (can't include)
- Else: dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]])
Step 4: Fill table:
Item 1 (w=2,v=3): dp[1][2]=3, dp[1][3]=3, dp[1][4]=3, dp[1][5]=3
Item 2 (w=3,v=4): dp[2][3]=max(3,4)=4, dp[2][5]=max(3,3+4)=7
Item 3 (w=4,v=5): dp[3][4]=max(3,5)=5, dp[3][5]=max(7,3+5)=8
Step 5: Answer is dp[3][5] = 8
Selected items: Item 1 + Item 2 (weight 2+3=5, value 3+4=7)... Recheck: actually 7.
Correct: dp[2][5] = max(dp[1][5]=3, 4+dp[1][2]=4+3=7) = 7
Final answer: 7 (Items 1 and 2)
Example 4
Apply Merge Sort to array [64, 34, 25, 12, 22, 11, 90]. Show steps.
Step 1: Divide phase (recursively split until single elements):
[64,34,25,12,22,11,90] -> [64,34,25,12] + [22,11,90]
-> [64,34] + [25,12] + [22,11] + [90]
-> [64] + [34] + [25] + [12] + [22] + [11] + [90]
Step 2: Merge phase (combine sorted subarrays):
[64]+[34]->[34,64]; [25]+[12]->[12,25]; [22]+[11]->[11,22]; [90]
[34,64]+[12,25]->[12,25,34,64]; [11,22]+[90]->[11,22,90]
[12,25,34,64]+[11,22,90]->[11,12,22,25,34,64,90]
Step 3: Final sorted array: [11, 12, 22, 25, 34, 64, 90]
Step 4: Comparisons: ~n log n = 7 x 3 = 21 (approximate)
Time complexity: O(n log n) = O(7 x log 7) ~= O(7 x 3) comparisons.
Representative solved questions
See the kind of question in this topic before opening the full practice set.
Question 1
What is the time complexity of Bubble Sort in the worst case?
O(n)
O(n log n)
O(n^2)
O(log n)
Answer: C. O(n^2)
ExplanationStep 1: Bubble Sort compares adjacent elements and swaps them if they are in the wrong order.
Step 2: In the worst case (reverse sorted array), it needs to make n-1 passes through the array.
Step 3: Each pass compares n-1, n-2, n-3... elements.
Step 4: Total comparisons = (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n^2).
Answer: O(n^2)
Sources and review notes
This is an AISEA-authored practice question.
Review status: accepted · Reviewed 2026-08-13 · structure and answer-key checks, editorial quality checks, duplicate screening
Question 2
Which sorting algorithm has the best average-case time complexity?
Quick Sort
Merge Sort
Heap Sort
All have O(n log n)
Answer: D. All have O(n log n)
ExplanationStep 1: Quick Sort has average case O(n log n) but worst case O(n^2).
Step 2: Merge Sort has guaranteed O(n log n) in all cases.
Step 3: Heap Sort has guaranteed O(n log n) in all cases.
Step 4: Merge Sort and Heap Sort have O(n log n) worst case, Quick Sort has O(n log n) average case.
Answer: All have O(n log n) average case
Sources and review notes
This is an AISEA-authored practice question.
Review status: accepted · Reviewed 2026-08-13 · structure and answer-key checks, editorial quality checks, duplicate screening
Question 3
What is the space complexity of Merge Sort?
O(1)
O(log n)
O(n)
O(n^2)
Answer: C. O(n)
ExplanationStep 1: Merge Sort uses the divide-and-conquer approach.
Step 2: It recursively divides the array into halves.
Step 3: During the merge phase, it needs temporary storage to hold the merged elements.
Step 4: The merge process requires O(n) additional space for the temporary array.
Answer: O(n)
Common mistakes and useful habits
- 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.
Ready to test your understanding?
Work through 105 questions with explanations after each answer.