Algorithms Space & Time Complexity Analysis 1 — Questions and Answers
Question 1: What is the time complexity of binary search on a sorted array of n elements?
- O(n)
- O(n log n)
- O(log n) (Correct answer)
- O(1)
Correct answer: O(log n)
Binary search halves the search space each iteration, resulting in O(log n) comparisons.
Question 2: Which Big-O notation describes the worst-case time complexity of bubble sort?
- O(n log n)
- O(n²) (Correct answer)
- O(n)
- O(log n)
Correct answer: O(n²)
Bubble sort requires nested loops, each running up to n iterations, yielding O(n²) in the worst case.
Question 3: An algorithm with O(1) space complexity means:
- It uses memory proportional to input size
- It requires no memory at all
- It uses a constant amount of extra memory regardless of input size (Correct answer)
- It uses logarithmic extra memory
Correct answer: It uses a constant amount of extra memory regardless of input size
O(1) space (constant space) means the algorithm uses a fixed amount of additional memory that does not grow with input size.
Question 4: What is the time complexity of accessing an element by index in a dynamic array (e.g., Python list)?
- O(log n)
- O(n)
- O(n²)
- O(1) (Correct answer)
Correct answer: O(1)
Dynamic arrays store elements contiguously in memory, so index-based access is a direct memory lookup in O(1).
Question 5: The recurrence T(n) = 2T(n/2) + O(n) describes which well-known algorithm's complexity?
- Insertion sort
- Merge sort (Correct answer)
- Selection sort
- Linear search
Correct answer: Merge sort
Merge sort divides the array into two halves (2T(n/2)) and then merges them in O(n), matching this recurrence whose solution is O(n log n).
Question 6: Which of the following time complexities grows the fastest as n increases?
- O(n log n)
- O(n²)
- O(2ⁿ) (Correct answer)
- O(n³)
Correct answer: O(2ⁿ)
Exponential O(2ⁿ) grows far faster than any polynomial, including O(n³), for sufficiently large n.
Question 7: What does the Master Theorem primarily help determine?
- The correctness of a recursive algorithm
- The time complexity of divide-and-conquer recurrences (Correct answer)
- The optimal base case for recursion
- The space used by a recursive call stack
Correct answer: The time complexity of divide-and-conquer recurrences
The Master Theorem provides a formula for solving recurrences of the form T(n) = aT(n/b) + f(n), common in divide-and-conquer algorithms.
Algorithms Space & Time Complexity Analysis 1
What is the time complexity of binary search on a sorted array of n elements?