Multiple Choice Questions (60)

1. Which statement best explains why asymptotic analysis ignores constant

coefficients?

A. Constants vary between programming languages

B. Constants dominate performance for small inputs
C. Constants become insignificant compared to dominant terms as input grows
D. Constants depend on compiler optimizations

2. An algorithm with running time

T(n) = 7n³ + 2n² + 100n + 50

belongs to which asymptotic class?
A. Θ(n²)
B. O(n³) only
C. Θ(n³)
D. Ω(n²) only

3. Which of the following best distinguishes an algorithm from a program?

A. Algorithms are always faster

B. Programs are language-independent
C. Algorithms are abstract, programs are concrete implementations
D. Programs cannot be analyzed

4. Why is worst-case analysis most commonly used in algorithm evaluation?

A. It always gives the fastest runtime

B. It is easier than best-case analysis
C. It guarantees an upper bound regardless of input
D. It ignores input size

5. Which condition must hold for a function f(n) to be in Θ(g(n))?

A. f(n) ≤ c·g(n) for all n

B. c₁g(n) ≤ f(n) ≤ c₂g(n) for sufficiently large n
C. f(n) grows faster than g(n)
D. f(n) = g(n) for all n
6. Which property ensures that every step of an algorithm has exactly one
meaning?

A. Finiteness
B. Effectiveness
C. Definiteness
D. Completeness

7. In Big-O notation, which element primarily defines scalability?

A. Constant factors
B. Lower-order terms
C. Dominant term
D. Hardware configuration

8. Which scenario represents a time–space trade-off?

A. Using recursion instead of iteration

B. Using dynamic programming to avoid recomputation
C. Choosing a faster CPU
D. Optimizing compiler flags

9. Which asymptotic notation gives a lower bound on growth?

A. O
B. Θ
C. Ω
D. o

10. Why is clock-time considered unreliable for algorithm comparison?

A. It is too precise
B. It ignores input size
C. It depends on external and machine-specific factors
D. It cannot measure memory usage

11. Which of the following inputs produces the worst-case for linear search?

A. Element at first index

B. Element at middle index
C. Element at last index
D. Element not present in the array
12. Which statement about average-case analysis is correct?

A. It always equals worst-case

B. It assumes a known probability distribution of inputs
C. It ignores all input variations
D. It is easier than worst-case analysis

13. Which algorithm property ensures it solves the entire problem and not just
part of it?

A. Correctness
B. Completeness
C. Effectiveness
D. Efficiency

14. For which reason is Θ-notation considered stronger than O-notation?

A. It gives only an upper bound

B. It gives only a lower bound
C. It provides a tight bound
D. It applies only to algorithms

15. Which resource is most commonly measured in algorithm analysis?

A. Disk usage
B. Network bandwidth
C. Execution time
D. Power consumption

16. Why is best-case analysis often considered misleading?

A. It overestimates performance
B. It provides no useful performance guarantee
C. It is mathematically complex
D. It applies only to sorting algorithms

17. Which mathematical tool is LEAST relevant for algorithm analysis?

A. Probability theory
B. Algebraic manipulation
C. Trigonometry
D. Combinatorics
18. If f(n) = 4n² + 10n + 6, which is the tightest asymptotic classification?

A. O(n²)
B. Ω(n)
C. Θ(n²)
D. Θ(n)

19. Which statement about Big-Omega is TRUE?

A. It represents worst-case performance

B. It provides an upper bound
C. It guarantees a minimum growth rate
D. It ignores constant factors only

20. Which operation has O(1) time complexity?

A. Searching an unsorted array

B. Iterating through an array
C. Accessing an array element by index
D. Sorting an array

21. A recurrence relation primarily helps in algorithm analysis because it:

A. Eliminates the need for base cases

B. Describes memory allocation directly
C. Expresses total running time in terms of smaller inputs
D. Converts recursive code into iterative code

22. In the recurrence

[T(n) = aT(n/b) + f(n)]

what does f(n) represent?

A. Time spent in recursive calls
B. Time spent solving the base case
C. Time spent outside recursion at each level
D. Space complexity of the algorithm

23. Which of the following recurrences represents a recursive linear search?

A. T(n) = 2T(n/2) + Θ(n)

B. T(n) = T(n−1) + Θ(1)
C. T(n) = T(n/2) + Θ(1)
D. T(n) = 2T(n/3) + Θ(n)
24. Why do recurrences naturally arise in divide-and-conquer algorithms?

A. Because loops are converted to recursion

B. Because problems are solved iteratively
C. Because the problem is split into smaller instances of itself
D. Because recursion always reduces time complexity

25. Which condition must be present for the Master Method to be applicable?

A. f(n) must be constant

B. Subproblems must be of unequal sizes
C. Recurrence must be of the form aT(n/b) + f(n)
D. Base case must be n = 0

26. In Merge Sort, which step primarily contributes to f(n) in the recurrence?

A. Dividing the array

B. Recursive calls
C. Merging sorted subarrays
D. Checking the base condition

27. The recurrence for Merge Sort is:

A. T(n) = T(n−1) + Θ(n)

B. T(n) = 2T(n/2) + Θ(n)
C. T(n) = T(n/2) + Θ(1)
D. T(n) = 4T(n/2) + Θ(1)

28. Which Master Method case applies when

[f(n) = Θ(n^{\log_b a})]?

A. Case 1 – recursion dominates

B. Case 2 – balanced case
C. Case 3 – extra work dominates
D. Master Method not applicable
29. If

[T(n) = 2T(n/2) + n^2]

which part dominates the runtime?

A. Recursive calls
B. Base case
C. Extra (non-recursive) work
D. Division step

30. Which recurrence solution technique relies on guessing and mathematical

induction?

A. Recursion tree method

B. Iteration method
C. Substitution method
D. Master method

31. What does the recursion-tree method primarily visualize?

A. Stack memory usage

B. Depth of recursion only
C. Cost incurred at each recursion level
D. Base case execution time

32. In the Master Method, what does

[n^{\log_b a}]
represent?

A. Cost of merging
B. Cost of dividing
C. Total cost of recursive calls
D. Base case complexity

33. Which algorithm demonstrates a single sub problem of size n−1?

A. Merge Sort
B. Binary Search
C. Linear Search (recursive)
D. Matrix Multiplication
34. Why is the base case essential in a recurrence?

A. It reduces memory usage

B. It prevents infinite recursion
C. It increases performance
D. It determines f(n)

35. Which statement about recurrences is TRUE?

A. They only apply to sorting algorithms

B. They cannot model space complexity
C. They mathematically describe self-referential processes
D. They replace Big-O notation

36. Which Master Method case applies when

[f(n) < n^{\log_b a}]?

A. Case 1
B. Case 2
C. Case 3
D. Iteration case

37. The recurrence

[T(n) = T(n/2) + Θ(1)]

most closely represents:

A. Merge Sort
B. Binary Search
C. Linear Search
D. Bubble Sort

38. In divide-and-conquer, “combine” refers to:

A. Solving base cases

B. Splitting the problem
C. Merging subproblem solutions
D. Reducing recursion depth
39. Which method repeatedly expands the recurrence until no T( ) terms
remain?

A. Substitution
B. Master
C. Iteration
D. Recursion tree

40. Which component of Merge Sort uses additional space?

A. Recursive calls
B. Comparison logic
C. Temporary arrays during merging
D. Base condition

41. Which statement best explains why Selection Sort has the same best-case and worst-case time
complexity?
A. It performs swaps even when data is sorted
B. It always scans the unsorted subarray to find the minimum
C. It uses nested loops regardless of input order
D. It repeatedly compares adjacent elements

42. In Bubble Sort, which condition ensures the largest element reaches its correct position after
each pass?

A. The swap operation

B. The number of elements
C. Adjacent comparison
D. The inner loop boundary shrinking

43. Which sorting algorithm described is adaptive based on input order?

A. Selection Sort
B. Bubble Sort
C. Insertion Sort
D. All of the above

44. Which property of Insertion Sort results in O(n) best-case time complexity?
A. Recursive calls
B. No shifting when array is sorted
C. Reduced comparisons
D. Single pass traversal
45. Which scenario represents the worst case for Linear Search?
A. Target at first index
B. Target at middle index
C. Target absent from the list
D. Target at random index

46. Why can Binary Search NOT be applied to unsorted data?

A. It requires random access
B. It relies on middle element comparison logic
C. It has logarithmic complexity
D. It divides data unevenly

47. Which statement about Bubble Sort is incorrect according to the document?
A. Worst-case complexity is O(n²)
B. Best-case complexity is O(n)
C. It compares adjacent elements
D. Largest element moves to end after each pass

48. In Binary Search, the search interval reduces by approximately:

A. One element
B. Two elements
C. Half each iteration
D. Log₂ n elements

49. Which algorithm benefits MOST from sorted data?

A. Linear Search
B. Selection Sort
C. Bubble Sort
D. Binary Search

50. Which algorithm guarantees the same number of comparisons regardless of input order?
A. Insertion Sort
B. Bubble Sort
C. Selection Sort
D. Binary Search

51. In heap data structures, priority is determined primarily by:

A. Node depth
B. Parent–child relationship
C. Heap property
D. Tree balance
52. Which heap type is ideal for emergency patient management systems?
A. Min Heap
B. Max Heap
C. Binary Search Tree
D. Hash Table

53. What causes a collision in a hash table?

A. Same value stored twice
B. Hash function error
C. Two keys map to the same index
D. Table overflow

54. Which data structure maintains hierarchical order and sorted data simultaneously?
A. Heap
B. Hash Table
C. Binary Search Tree
D. Array

55. Which traversal characteristic ensures Binary Search Tree efficiency?

A. Complete binary structure
B. Sorted left–right property
C. Balanced height
D. Heap ordering

56. Which algorithm shows poor scalability for large datasets?

A. Binary Search
B. Insertion Sort
C. QuickSort
D. MergeSort

57. Which factor primarily distinguishes advanced algorithms from simple algorithms?
A. Implementation language
B. Space usage only
C. Optimized time complexity
D. Input size

58. Which algorithm is both in-place and comparison-based?

A. Bubble Sort
B. Hash Table
C. Binary Search
D. Heap
59. What is the key limitation of Linear Search?
A. Requires sorted data
B. High space complexity
C. Time complexity grows linearly
D. Cannot locate missing elements

60. Which Java Binary Search variable controls the lower bound of the search range?
A. mid
B. h
C. l
D. n

True / False Questions (30)

1. Θ-notation ignores both lower-order terms and constant coefficients.
2. An algorithm may be correct but not finite.
3. Worst-case analysis provides a performance guarantee.
4. Average-case analysis assumes all inputs occur with equal probability unless specified.
5. Big-O and Θ always describe the same growth rate.
6. Space complexity measures memory usage relative to input size.
7. Best-case complexity usually reflects real-world performance.
8. Asymptotic notation applies only to time complexity.
9. Using more memory can sometimes reduce execution time.
10. Algorithm analysis depends on processor speed.
11. A recurrence always includes at least one base case.
12. Recurrences are the mathematical equivalent of recursion.
13. Master Method can solve all possible recurrences.
14. Merge Sort creates two sub problems of equal size.
15. Binary Search reduces the problem size by half each step.
16. The substitution method requires drawing a recursion tree.
17. In Case 3 of the Master Method, f(n) dominates the recurrence.
18. A recurrence can describe space complexity as well as time complexity.
19. Without a base case, a recurrence cannot be solved.
20. Divide-and-conquer algorithms never require extra memory.
21. Selection Sort reduces execution time when the array is already sorted.
22. Binary Search always performs faster than Linear Search regardless of data order.
23. Insertion Sort shifts elements only when necessary.
24. Bubble Sort requires fewer comparisons in its best case than worst case.
25. Hash tables provide direct access using keys.
26. Heaps are complete binary trees.
27. Binary Search Tree guarantees balanced height.
28. Sorting improves the efficiency of searching algorithms.
29. Advanced algorithms always consume less memory than simple algorithms.
30. Binary Search can return −1 if the element is not found.
Matching Questions (27)
Match Column A with the MOST appropriate item in Column B

Column A Column B
1. Big-O A. Tight bound
2. Big-Ω B. Lower bound
3. Θ-notation C. Upper bound
4. Finiteness D. Algorithm halts
5. Definiteness E. Unambiguous steps
6. Worst-case analysis F. Performance guarantee
7. Average-case analysis G. Expected performance
8. Space complexity H. Memory usage
9. Time complexity I. Execution time growth
10. Order of growth J. Dominant term behavior
11. Recurrence relation K. Defines a value using smaller inputs
12. Base case L. Stops recursion
13. Master method Case 1 M. Non-recursive work
14. Master method Case 2 N. Number of sub problems
15. Master method Case 3 O. Sub problem size factor
16. Merge Sort P. Recursion dominates
17. Binary Search Q. Balanced work
18. Selection Sort R. Extra work dominates
19. Bubble Sort S. Divide-and-conquer algorithm
20. Insertion Sort T. Logarithmic recurrence
21. Linear Search U. Priority-based execution
22. Binary Search V. Key–value mapping
23. Heap W. O(log n) search
24. Hash Table X. Adjacent comparisons
25. Binary Search Tree Y. Hierarchical structure
26. Worst-case Linear Search Z. Non-adaptive sorting
27. Sorting AA. Best-case O(n)
BB. Sequential comparison
CC. Element not found
DD. Improves data efficiency