Algorithms MCQs with answers and time complexity

Review searching, sorting, algorithm design and time complexity, then answer questions with explanations. Practise choosing an approach and explaining its cost for placement and GATE CS concept preparation.

185 practice questionsPage updated 24 Sept 2026Review metadata pendingPractice questions

Practise this concept

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

8 rules

Time Complexity Growth: $O (1) < O (lo g n) < O (n) < O (n) < O (n lo g n) < O (n^{2}) < O (n^{3}) < O (2^{n}) < O (n!)$

Master Theorem: For $T (n) = a T (n / b) + O (n^{k})$ : compare $k$ and $lo g_{b} a$ to yield $O (n^{k})$ , $O (n^{k} lo g n)$ , or $O (n^{l o g_{b} a})$

Binary Search: $T (n) = T (n /2) + O (1) ⟹ O (lo g n)$ time and $O (1)$ space on sorted arrays

Merge Sort: $T (n) = 2 T (n /2) + O (n) ⟹ O (n lo g n)$ time in all cases, requires $O (n)$ auxiliary space

Quick Sort: Recurrence $T (n) = T (k) + T (n - k - 1) + O (n) ⟹ O (n lo g n)$ average time, $O (n^{2})$ worst case, $O (lo g n)$ recursion stack space

Elementary Sorts: Bubble, Selection, and Insertion sorts run in $O (n^{2})$ worst-case time with $O (1)$ auxiliary space

Graph Traversals: BFS and DFS visit all reachable nodes in $O (V + E)$ time and $O (V)$ space using adjacency lists

Dynamic Programming: Solves problems with optimal substructure and overlapping subproblems using memoization (top-down) or tabulation (bottom-up)

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( $lo g n$ ) is logarithmic (binary search), O(n) is linear (single loop), O(n $lo g 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 $lo g n$ )), Quick Sort (pivot partitioning, average O(n $lo g 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 $lo g 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( $lo g 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 $lo g 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.

Check the idea while it is fresh.Open a focused exercise without losing this article.Practise this concept

Worked examples

Example 1

What is the time complexity of the following nested loop?

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        sum += arr[i][j];
    }
}

Solution

Step 1: Outer loop iteration count.
The outer loop executes $n$ times ( $i = 0, 1, \dots, n - 1$ ).

Step 2: Inner loop execution per outer iteration.
For each outer iteration, the inner loop executes $n$ times.

Step 3: Total elementary operations.

Total = i = 0 \sum n - 1 j = 0 \sum n - 1 1 = n \times n = n^{2}

Each inner operation runs in $O (1)$ constant time.

Answer: $O (n^{2})$ (quadratic time complexity).

Example 2

Apply binary search to locate target key 23 in the sorted array: [2, 5, 8, 12, 16, 23, 38, 45, 56].

Solution

Step 1: Iteration 1.

low = 0, high = 8 ⟹ mid = ⌊ \frac{0 + 8}{2} ⌋ = 4

arr [4] = 16 < 23 ⟹ Search right half: low = 5, high = 8

Step 2: Iteration 2.

mid = ⌊ \frac{5 + 8}{2} ⌋ = 6

arr [6] = 38 > 23 ⟹ Search left half: low = 5, high = 5

Step 3: Iteration 3.

mid = ⌊ \frac{5 + 5}{2} ⌋ = 5

arr [5] = 23 = target key!

Answer: Target found at index 5 after 3 comparisons.

Example 3

Solve the 0/1 Knapsack problem with capacity $W = 5$ and items: [(wt: 2, val: 3), (wt: 3, val: 4), (wt: 4, val: 5)].

Solution

Step 1: Define DP state.
Let $d p [i] [w]$ denote maximum value obtainable using a subset of the first $i$ items with capacity $w$ .

d p [i] [w] = max {d p [i - 1] [w], d p [i - 1] [w - w t_{i}] + v a l_{i}}

Step 2: DP table computation.
- Capacity 0 to 5 for Item 1 ( $w t = 2, v a l = 3$ ): dp[1] = [0, 0, 3, 3, 3, 3]
- Capacity 0 to 5 for Item 2 ( $w t = 3, v a l = 4$ ): dp[2] = [0, 0, 3, 4, 4, 7] (at $w = 5$ : $max (3, 3 + 4) = 7$ )
- Capacity 0 to 5 for Item 3 ( $w t = 4, v a l = 5$ ): dp[3][5] = \max(7, dp[2][1] + 5) = \max(7, 0 + 5) = 7

Answer: Maximum knapsack value is 7 (taking items 1 and 2 with weights $2 + 3 = 5$ ).

Example 4

State the recurrence relation and overall time complexity for Merge Sort.

Solution

Step 1: Recurrence formulation.
Merge sort divides the array into 2 equal halves and merges them in linear time:

T (n) = 2 T (\frac{n}{2}) + O (n)

Step 2: Apply Master Theorem.
Here $a = 2, b = 2, k = 1$ .

lo g_{b} a = lo g_{2} 2 = 1 = k ⟹ T (n) = O (n lo g n)

Answer: $O (n lo g n)$ in best, average, and worst cases.

Representative solved questions

See the kind of question in this topic before opening the full practice set.

Question 1

Which sorting algorithm has the best average-case time complexity?

Quick Sort
Merge Sort
Heap Sort
All have O(n $lo g n$ )

Answer: D. All have O(n log n)

Explanation

Step 1: Quick Sort has average case O(n $lo g n$ ) but worst case $O (n^{2})$ .
Step 2: Merge Sort has guaranteed O(n $lo g n$ ) in all cases.
Step 3: Heap Sort has guaranteed O(n $lo g n$ ) in all cases.
Step 4: Merge Sort and Heap Sort have O(n $lo g n$ ) worst case, Quick Sort has O(n $lo g n$ ) average case.
Answer: All have O(n $lo g 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 2

What is the recurrence relation for the time complexity of Merge Sort?

$T (n) = T (n /2) + O (n)$
$T (n) = 2 T (n /2) + O (n)$
$T (n) = 2 T (n /2) + O (1)$
$T (n) = T (n - 1) + O (n)$

Answer: B. T(n) = 2T(n/2) + O(n)

Explanation

Step 1: Merge Sort divides the problem into 2 subproblems of size n/2.
Step 2: The conquer step recursively sorts both halves.
Step 3: The merge step combines two sorted halves in O(n) time.
Step 4: Using Master Theorem: $a = 2$ , $b = 2$ , $f (n) = O (n)$ , so T(n) = 2T(n/2) + $O (n) = O (n lo g n)$ .
Answer: T(n) = 2T(n/2) + O(n)

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

How does randomized Quick Sort improve performance?

It reduces comparisons
It avoids worst-case by random pivot selection
It uses less memory
It works on unsorted arrays

Answer: B. It avoids worst-case by random pivot selection

Explanation

Step 1: Standard Quick Sort can hit $O (n^{2})$ with poor pivot choices.
Step 2: Randomized Quick Select selects a random element as pivot.
Step 3: This makes the probability of consistently bad pivots extremely low.
Step 4: Expected time complexity becomes O(n $lo g n$ ) regardless of input distribution.
Answer: It avoids worst-case by random pivot selection

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

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 185 questions with explanations after each answer.

Start practice

Next topic: DBMS