1|Page
CSE 310 DATA STRUCTURES AND
ALGORITHMS FINAL EXAMINATION: STUDY
GUIDE | LATEST UPDATE 2026/2027 |
PRACTICE QUESTIONS AND ANSWERS |
EXAM REVIEW
TABLE OF CONTENTS
I. Asymptotic Notation and Algorithm Analysis
II. Sorting Algorithms and Lower Bounds
III. Heaps and Heap Operations
IV. Hash Tables and Hashing
V. Binary Search Trees and Balanced Trees
VI. Disjoint Sets and Union-Find
VII. Dynamic Programming
VIII. Greedy Algorithms
IX. Graph Algorithms: Traversal, MST, and Shortest Paths
X. Algorithm Design Paradigms and Complexity Comparison
,2|Page
question 1: What is the primary purpose of asymptotic notation in algorithm analysis?
Correct Answer: To describe the growth rate of an algorithm's running time or space
usage as the input size grows, independent of machine-specific constants.
Asymptotic notation abstracts away constant factors and lower-order terms, focusing on how
performance scales with input size. This allows comparison of algorithms across different
hardware and implementations. Big-O, Big-Omega, and Big-Theta are the standard
notations.
question 2: What does O(g(n)) represent?
Correct Answer: The set of functions f(n) for which there exist positive constants c and
n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀.
Big-O provides an asymptotic upper bound on a function. It describes the worst-case growth
rate. For example, 3n² + 5n + 2 is O(n²). Big-O is the most commonly used notation for
expressing algorithm complexity.
question 3: What does Ω(g(n)) represent?
Correct Answer: The set of functions f(n) for which there exist positive constants c and
n₀ such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n₀.
Big-Omega provides an asymptotic lower bound. It describes the best-case growth rate or a
minimum performance guarantee. For example, any comparison-based sorting algorithm is
Ω(n log n).
question 4: What does Θ(g(n)) represent?
Correct Answer: The set of functions f(n) for which there exist positive constants c₁, c₂,
and n₀ such that 0 ≤ c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀.
Big-Theta provides a tight bound, meaning f(n) grows at the same rate as g(n) asymptotically.
If f(n) = Θ(g(n)), then f(n) is both O(g(n)) and Ω(g(n)). For example, 2n² + 3n = Θ(n²).
question 5: What is the difference between worst-case and average-case analysis?
Correct Answer: Worst-case analysis considers the maximum running time over all
inputs of size n, while average-case analysis considers the expected running time
assuming a probability distribution over inputs.
,3|Page
Worst-case analysis provides a performance guarantee and is often easier to compute.
Average-case analysis is more realistic but requires assumptions about input distribution. For
example, quicksort has O(n²) worst-case but O(n log n) average-case.
question 6: What is the runtime of the following code fragment in Big-O notation? for (int i =
0; i < n; i++) { for (int j = 0; j < n; j++) { sum += i * j; } }
Correct Answer: O(n²)
The outer loop runs n times, and for each iteration, the inner loop runs n times. The total
number of operations is n × n = n². Nested loops multiply their iteration counts. This is a
classic quadratic-time algorithm.
question 7: What is the runtime of the following code fragment in Big-O notation? for (int i =
0; i < n; i++) { sum += i; }
Correct Answer: O(n)
The loop runs n times, performing a constant amount of work per iteration. The total work is
proportional to n. This is a linear-time algorithm. Adding another independent loop of n
iterations would still be O(n).
question 8: What is the runtime of the following code fragment in Big-O notation? for (int i =
1; i < n; i = i * 2) { sum += i; }
Correct Answer: O(log n)
The loop variable i doubles each iteration: 1, 2, 4, 8, ... until reaching n. The number of
iterations is the number of times you can double 1 before reaching n, which is log₂(n).
Logarithmic algorithms are highly efficient.
question 9: What is the recurrence relation for merge sort?
Correct Answer: T(n) = 2T(n/2) + Θ(n)
Merge sort divides the array into two halves, recursively sorts each half, and merges the
sorted halves. The divide step takes constant time, the conquer step solves two subproblems
of size n/2, and the combine step (merge) takes Θ(n) time. The solution to this recurrence is
Θ(n log n).
question 10: What is the solution to the recurrence T(n) = 2T(n/2) + Θ(n)?
, 4|Page
Correct Answer: Θ(n log n)
This recurrence describes merge sort. Using the Master Theorem: a = 2, b = 2, f(n) = Θ(n).
Since n^(log₂2) = n¹ = n, and f(n) = Θ(n), we are in Case 2. The solution is Θ(n log n).
question 11: What is the solution to the recurrence T(n) = T(n/2) + Θ(1)?
Correct Answer: Θ(log n)
This recurrence describes binary search. The problem size is halved each time, with constant
work per level. The recursion depth is log n. Using the Master Theorem: a = 1, b = 2, f(n) =
Θ(1). Since n^(log₂1) = n⁰ = 1, and f(n) = Θ(1), we are in Case 2. The solution is Θ(log n).
question 12: What is the solution to the recurrence T(n) = 2T(n/2) + Θ(n²)?
Correct Answer: Θ(n²)
Using the Master Theorem: a = 2, b = 2, f(n) = Θ(n²). Since n^(log₂2) = n¹ = n, and f(n) =
Θ(n²) grows faster than n, we are in Case 3. The solution is Θ(f(n)) = Θ(n²).
question 13: What is the solution to the recurrence T(n) = 7T(n/2) + Θ(n²)?
Correct Answer: Θ(n^(log₂7)) ≈ Θ(n^2.807)
Using the Master Theorem: a = 7, b = 2, f(n) = Θ(n²). Since n^(log₂7) ≈ n^2.807 grows faster
than n², we are in Case 1. The solution is Θ(n^(log₂7)).
question 14: What is the substitution method for solving recurrences?
Correct Answer: A method where you guess the form of the solution and then use
mathematical induction to prove the guess correct.
The substitution method requires intuition to guess the solution, often based on similar
recurrences. You then verify the guess by substituting it into the recurrence and proving the
bound holds. It is more rigorous than the Master Theorem but requires more effort.
question 15: What is the Master Theorem?
Correct Answer: A cookbook method for solving recurrences of the form T(n) = aT(n/b)
+ f(n), where a ≥ 1, b > 1, and f(n) is asymptotically positive.
CSE 310 DATA STRUCTURES AND
ALGORITHMS FINAL EXAMINATION: STUDY
GUIDE | LATEST UPDATE 2026/2027 |
PRACTICE QUESTIONS AND ANSWERS |
EXAM REVIEW
TABLE OF CONTENTS
I. Asymptotic Notation and Algorithm Analysis
II. Sorting Algorithms and Lower Bounds
III. Heaps and Heap Operations
IV. Hash Tables and Hashing
V. Binary Search Trees and Balanced Trees
VI. Disjoint Sets and Union-Find
VII. Dynamic Programming
VIII. Greedy Algorithms
IX. Graph Algorithms: Traversal, MST, and Shortest Paths
X. Algorithm Design Paradigms and Complexity Comparison
,2|Page
question 1: What is the primary purpose of asymptotic notation in algorithm analysis?
Correct Answer: To describe the growth rate of an algorithm's running time or space
usage as the input size grows, independent of machine-specific constants.
Asymptotic notation abstracts away constant factors and lower-order terms, focusing on how
performance scales with input size. This allows comparison of algorithms across different
hardware and implementations. Big-O, Big-Omega, and Big-Theta are the standard
notations.
question 2: What does O(g(n)) represent?
Correct Answer: The set of functions f(n) for which there exist positive constants c and
n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀.
Big-O provides an asymptotic upper bound on a function. It describes the worst-case growth
rate. For example, 3n² + 5n + 2 is O(n²). Big-O is the most commonly used notation for
expressing algorithm complexity.
question 3: What does Ω(g(n)) represent?
Correct Answer: The set of functions f(n) for which there exist positive constants c and
n₀ such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n₀.
Big-Omega provides an asymptotic lower bound. It describes the best-case growth rate or a
minimum performance guarantee. For example, any comparison-based sorting algorithm is
Ω(n log n).
question 4: What does Θ(g(n)) represent?
Correct Answer: The set of functions f(n) for which there exist positive constants c₁, c₂,
and n₀ such that 0 ≤ c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀.
Big-Theta provides a tight bound, meaning f(n) grows at the same rate as g(n) asymptotically.
If f(n) = Θ(g(n)), then f(n) is both O(g(n)) and Ω(g(n)). For example, 2n² + 3n = Θ(n²).
question 5: What is the difference between worst-case and average-case analysis?
Correct Answer: Worst-case analysis considers the maximum running time over all
inputs of size n, while average-case analysis considers the expected running time
assuming a probability distribution over inputs.
,3|Page
Worst-case analysis provides a performance guarantee and is often easier to compute.
Average-case analysis is more realistic but requires assumptions about input distribution. For
example, quicksort has O(n²) worst-case but O(n log n) average-case.
question 6: What is the runtime of the following code fragment in Big-O notation? for (int i =
0; i < n; i++) { for (int j = 0; j < n; j++) { sum += i * j; } }
Correct Answer: O(n²)
The outer loop runs n times, and for each iteration, the inner loop runs n times. The total
number of operations is n × n = n². Nested loops multiply their iteration counts. This is a
classic quadratic-time algorithm.
question 7: What is the runtime of the following code fragment in Big-O notation? for (int i =
0; i < n; i++) { sum += i; }
Correct Answer: O(n)
The loop runs n times, performing a constant amount of work per iteration. The total work is
proportional to n. This is a linear-time algorithm. Adding another independent loop of n
iterations would still be O(n).
question 8: What is the runtime of the following code fragment in Big-O notation? for (int i =
1; i < n; i = i * 2) { sum += i; }
Correct Answer: O(log n)
The loop variable i doubles each iteration: 1, 2, 4, 8, ... until reaching n. The number of
iterations is the number of times you can double 1 before reaching n, which is log₂(n).
Logarithmic algorithms are highly efficient.
question 9: What is the recurrence relation for merge sort?
Correct Answer: T(n) = 2T(n/2) + Θ(n)
Merge sort divides the array into two halves, recursively sorts each half, and merges the
sorted halves. The divide step takes constant time, the conquer step solves two subproblems
of size n/2, and the combine step (merge) takes Θ(n) time. The solution to this recurrence is
Θ(n log n).
question 10: What is the solution to the recurrence T(n) = 2T(n/2) + Θ(n)?
, 4|Page
Correct Answer: Θ(n log n)
This recurrence describes merge sort. Using the Master Theorem: a = 2, b = 2, f(n) = Θ(n).
Since n^(log₂2) = n¹ = n, and f(n) = Θ(n), we are in Case 2. The solution is Θ(n log n).
question 11: What is the solution to the recurrence T(n) = T(n/2) + Θ(1)?
Correct Answer: Θ(log n)
This recurrence describes binary search. The problem size is halved each time, with constant
work per level. The recursion depth is log n. Using the Master Theorem: a = 1, b = 2, f(n) =
Θ(1). Since n^(log₂1) = n⁰ = 1, and f(n) = Θ(1), we are in Case 2. The solution is Θ(log n).
question 12: What is the solution to the recurrence T(n) = 2T(n/2) + Θ(n²)?
Correct Answer: Θ(n²)
Using the Master Theorem: a = 2, b = 2, f(n) = Θ(n²). Since n^(log₂2) = n¹ = n, and f(n) =
Θ(n²) grows faster than n, we are in Case 3. The solution is Θ(f(n)) = Θ(n²).
question 13: What is the solution to the recurrence T(n) = 7T(n/2) + Θ(n²)?
Correct Answer: Θ(n^(log₂7)) ≈ Θ(n^2.807)
Using the Master Theorem: a = 7, b = 2, f(n) = Θ(n²). Since n^(log₂7) ≈ n^2.807 grows faster
than n², we are in Case 1. The solution is Θ(n^(log₂7)).
question 14: What is the substitution method for solving recurrences?
Correct Answer: A method where you guess the form of the solution and then use
mathematical induction to prove the guess correct.
The substitution method requires intuition to guess the solution, often based on similar
recurrences. You then verify the guess by substituting it into the recurrence and proving the
bound holds. It is more rigorous than the Master Theorem but requires more effort.
question 15: What is the Master Theorem?
Correct Answer: A cookbook method for solving recurrences of the form T(n) = aT(n/b)
+ f(n), where a ≥ 1, b > 1, and f(n) is asymptotically positive.
