Data Structures and Algorithms Exam Practice
Questions And Correct Answers (Verified Answers)
Plus Rationale 2026 Q&A
1: COMPLEXITY ANALYSIS (BIG O NOTATION)
1. What is the time complexity of accessing an element by index in an array?
A) O(1)
B) O(n)
C) O(log n)
D) O(n²)
Correct Answer: A | Rationale: Arrays store elements in contiguous memory.
Accessing any element by its index requires a single calculation (base address +
index × element size), making it constant time O(1).
2. What is the time complexity of searching for an element in an unsorted array
using linear search?
A) O(1)
B) O(n)
C) O(log n)
D) O(n²)
Correct Answer: B | Rationale: In the worst case, linear search checks every
element in the array. If the target is the last element or not present, it performs n
comparisons, giving O(n) time complexity.
3. What is the time complexity of binary search on a sorted array?
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)
,Correct Answer: C | Rationale: Binary search halves the search space with each
step. After k steps, the remaining search space is n/2^k. Setting this to 1 gives k =
log₂(n). Thus, O(log n).
4. What is the space complexity of a recursive algorithm that uses O(n) call stack
depth?
A) O(1)
B) O(n)
C) O(log n)
D) O(n²)
Correct Answer: B | Rationale: Even if the algorithm uses no extra data structures,
recursion itself consumes memory on the call stack. If the recursion depth is n
(e.g., recursive factorial), the space complexity is O(n).
5. Which of the following has the best (lowest) time complexity for searching in
the average case?
A) Linear search in an unsorted array
B) Binary search in a sorted array
C) Searching in a linked list
D) Linear search in a sorted array
Correct Answer: B | Rationale: Binary search has O(log n) average time. Linear
search (A, C, D) has O(n) average time. O(log n) is significantly better than O(n) for
large n.
6. What is the time complexity of the following nested loop?
python
for i in range(n):
for j in range(n):
print(i, j)
A) O(n)
B) O(n log n)
,C) O(n²)
D) O(2ⁿ)
Correct Answer: C | Rationale: The outer loop runs n times. For each outer
iteration, the inner loop runs n times. Total operations = n × n = n², giving O(n²).
7. What is the time complexity of this code?
python
i=1
while i < n:
i=i*2
A) O(n)
B) O(log n)
C) O(n log n)
D) O(1)
Correct Answer: B | Rationale: The variable i doubles each iteration: 1, 2, 4, 8, ... It
reaches n in log₂(n) steps. Therefore, time complexity is O(log n).
8. Which complexity class grows the fastest?
A) O(1)
B) O(n)
C) O(n log n)
D) O(2ⁿ)
Correct Answer: D | Rationale: Exponential time O(2ⁿ) grows far faster than
polynomial (O(n), O(n log n)) or logarithmic (O(log n)). For n=10, 2¹⁰ = 1024, while
n²=100.
9. What is the time complexity of inserting an element at the beginning of a
dynamic array (ArrayList) in Java/Python list?
A) O(1)
B) O(n)
, C) O(log n)
D) O(n²)
Correct Answer: B | Rationale: Inserting at index 0 requires shifting all existing
elements one position to the right. This takes O(n) time in the worst case.
10. What is the time complexity of inserting an element at the end of an
ArrayList (amortized)?
A) O(1)
B) O(n)
C) O(log n)
D) O(n²)
Correct Answer: A | Rationale: Appending to the end is generally O(1).
Occasionally, when the array needs to resize, it's O(n), but the amortized (average)
time complexity is O(1).
11. The Master Theorem is used to solve recurrences of the form T(n) = aT(n/b) +
f(n). For what type of algorithms is this used?
A) Divide and conquer algorithms
B) Greedy algorithms
C) Dynamic programming
D) Brute force algorithms
Correct Answer: A | Rationale: The Master Theorem provides a cookbook solution
for recurrences arising from divide-and-conquer algorithms (e.g., Merge Sort: T(n)
= 2T(n/2) + O(n)).
12. What is the time complexity of Merge Sort?
A) O(n)
B) O(n log n)
C) O(n²)
D) O(log n)
Correct Answer: B | Rationale: Merge Sort divides the array into halves (log n
levels) and merges n elements at each level. Total work = n log n, so time
complexity is O(n log n) in all cases.
Questions And Correct Answers (Verified Answers)
Plus Rationale 2026 Q&A
1: COMPLEXITY ANALYSIS (BIG O NOTATION)
1. What is the time complexity of accessing an element by index in an array?
A) O(1)
B) O(n)
C) O(log n)
D) O(n²)
Correct Answer: A | Rationale: Arrays store elements in contiguous memory.
Accessing any element by its index requires a single calculation (base address +
index × element size), making it constant time O(1).
2. What is the time complexity of searching for an element in an unsorted array
using linear search?
A) O(1)
B) O(n)
C) O(log n)
D) O(n²)
Correct Answer: B | Rationale: In the worst case, linear search checks every
element in the array. If the target is the last element or not present, it performs n
comparisons, giving O(n) time complexity.
3. What is the time complexity of binary search on a sorted array?
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)
,Correct Answer: C | Rationale: Binary search halves the search space with each
step. After k steps, the remaining search space is n/2^k. Setting this to 1 gives k =
log₂(n). Thus, O(log n).
4. What is the space complexity of a recursive algorithm that uses O(n) call stack
depth?
A) O(1)
B) O(n)
C) O(log n)
D) O(n²)
Correct Answer: B | Rationale: Even if the algorithm uses no extra data structures,
recursion itself consumes memory on the call stack. If the recursion depth is n
(e.g., recursive factorial), the space complexity is O(n).
5. Which of the following has the best (lowest) time complexity for searching in
the average case?
A) Linear search in an unsorted array
B) Binary search in a sorted array
C) Searching in a linked list
D) Linear search in a sorted array
Correct Answer: B | Rationale: Binary search has O(log n) average time. Linear
search (A, C, D) has O(n) average time. O(log n) is significantly better than O(n) for
large n.
6. What is the time complexity of the following nested loop?
python
for i in range(n):
for j in range(n):
print(i, j)
A) O(n)
B) O(n log n)
,C) O(n²)
D) O(2ⁿ)
Correct Answer: C | Rationale: The outer loop runs n times. For each outer
iteration, the inner loop runs n times. Total operations = n × n = n², giving O(n²).
7. What is the time complexity of this code?
python
i=1
while i < n:
i=i*2
A) O(n)
B) O(log n)
C) O(n log n)
D) O(1)
Correct Answer: B | Rationale: The variable i doubles each iteration: 1, 2, 4, 8, ... It
reaches n in log₂(n) steps. Therefore, time complexity is O(log n).
8. Which complexity class grows the fastest?
A) O(1)
B) O(n)
C) O(n log n)
D) O(2ⁿ)
Correct Answer: D | Rationale: Exponential time O(2ⁿ) grows far faster than
polynomial (O(n), O(n log n)) or logarithmic (O(log n)). For n=10, 2¹⁰ = 1024, while
n²=100.
9. What is the time complexity of inserting an element at the beginning of a
dynamic array (ArrayList) in Java/Python list?
A) O(1)
B) O(n)
, C) O(log n)
D) O(n²)
Correct Answer: B | Rationale: Inserting at index 0 requires shifting all existing
elements one position to the right. This takes O(n) time in the worst case.
10. What is the time complexity of inserting an element at the end of an
ArrayList (amortized)?
A) O(1)
B) O(n)
C) O(log n)
D) O(n²)
Correct Answer: A | Rationale: Appending to the end is generally O(1).
Occasionally, when the array needs to resize, it's O(n), but the amortized (average)
time complexity is O(1).
11. The Master Theorem is used to solve recurrences of the form T(n) = aT(n/b) +
f(n). For what type of algorithms is this used?
A) Divide and conquer algorithms
B) Greedy algorithms
C) Dynamic programming
D) Brute force algorithms
Correct Answer: A | Rationale: The Master Theorem provides a cookbook solution
for recurrences arising from divide-and-conquer algorithms (e.g., Merge Sort: T(n)
= 2T(n/2) + O(n)).
12. What is the time complexity of Merge Sort?
A) O(n)
B) O(n log n)
C) O(n²)
D) O(log n)
Correct Answer: B | Rationale: Merge Sort divides the array into halves (log n
levels) and merges n elements at each level. Total work = n log n, so time
complexity is O(n log n) in all cases.
