Performance analysis: time and space complexity, asymptotic notation and recurrence relations. - Question Bank

1. Consider the recurrence T(n) = 3T(n/3) + n. What is the time complexity?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(n^3)
2. Which scenario best describes an algorithm with O(2^n) time complexity?
A) Binary Search
B) Linear Search
C) Brute-force Traveling Salesperson Problem solution
D) Merge Sort
3. What is the space complexity of a recursive function call stack if the maximum depth of recursion is 'n'?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
4. If an algorithm has a time complexity of O(n log n), and the input size is multiplied by 16, how does the execution time change approximately?
A) It increases by a factor of 16
B) It increases by a factor of 16 * log(16)
C) It doubles
D) It remains the same
5. Which of the following represents the tightest possible upper bound for the growth rate of a function?
A) Big O (O)
B) Big Omega (Ω)
C) Big Theta (Θ)
D) Little o (o)
6. What is the primary goal of performance analysis in algorithms?
A) To make algorithms run on any hardware
B) To determine the optimal algorithm for a given problem
C) To measure the exact time in milliseconds
D) To reduce the code size
7. What is the time complexity of inserting an element into a sorted array while maintaining the sorted order?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
8. Which asymptotic notation is used to describe the upper bound of growth rate?
A) Big Omega (Ω)
B) Big Theta (Θ)
C) Big O (O)
D) Little omega (ω)
9. If T(n) = 4T(n/2) + n, what is the time complexity according to the Master Theorem?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(n^3)
10. Consider a function that doubles its input size in each recursive call, and the work done at each step is constant: T(n) = T(n/2) + O(1). This is solved by which Master Theorem case?
A) Case 1
B) Case 2
C) Case 3
D) None of the above
11. What is the space complexity of an algorithm that uses a fixed number of variables, regardless of input size?
A) O(n)
B) O(log n)
C) O(1)
D) O(n^2)
12. What is the time complexity of finding the minimum element in an unsorted array?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
13. Which of the following is a characteristic of Little o notation (o)?
A) It denotes a tight bound.
B) It denotes a lower bound.
C) It denotes an upper bound that is not tight.
D) It denotes an average bound.
14. What is the lower bound of the time complexity of any comparison-based sorting algorithm?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(log n)
15. Which notation is used to denote the tight bound of an algorithm's growth rate?
A) Big O (O)
B) Big Omega (Ω)
C) Big Theta (Θ)
D) Little o (o)
16. If an algorithm's time complexity is O(n^3), and the input size increases from 10 to 20, by what factor does the execution time increase?
A) 2
B) 4
C) 8
D) 16
17. What does the recurrence T(n) = T(n/2) + O(1) represent?
A) Linear time complexity
B) Logarithmic time complexity
C) Quadratic time complexity
D) Constant time complexity
18. Consider the recurrence T(n) = 2T(n/2) + O(1). What is its solution?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(log n)
19. What is the time complexity of adding two numbers?
A) O(n)
B) O(log n)
C) O(1)
D) O(n^2)
20. Which of the following describes an algorithm that performs a fixed number of operations regardless of the input size?
A) O(n)
B) O(log n)
C) O(1)
D) O(n^2)
21. What is the time complexity of heap sort in the worst case?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(log n)
22. What is the space complexity of quicksort (in-place implementation, ignoring recursion stack)?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
23. What is the time complexity of quicksort in the worst case?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(log n)
24. What is the time complexity of quicksort in the average case?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(log n)
25. What is the space complexity of merge sort?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
26. What is the time complexity of merge sort in the worst case?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(log n)
27. What is the time complexity of bubble sort in the worst case?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(1)
28. Consider the recurrence T(n) = T(n-1) + O(n). What is its solution?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(log n)
29. What is the space complexity of storing 'n' elements in a hash table?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
30. What is the typical time complexity for inserting into a hash table?
A) O(n)
B) O(log n)
C) O(1) on average
D) O(n^2)
31. Which of the following has the worst time complexity for searching?
A) Balanced Binary Search Tree
B) Hash Table (with good hash function)
C) Unsorted Array
D) Sorted Array
32. What is the time complexity of deleting an element at the end of a singly linked list (without a tail pointer)?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
33. What is the time complexity of inserting an element at the beginning of a singly linked list?
A) O(n)
B) O(1)
C) O(log n)
D) O(n^2)
34. If T(n) = 2T(n/2) + O(n), what is the time complexity?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(log n)
35. Which case of the Master Theorem applies when f(n) = Θ(n^(log_b a))?
A) Case 1
B) Case 2
C) Case 3
D) None of the above
36. The Master Theorem is used to solve which type of problems?
A) Recurrence relations of the form T(n) = aT(n/b) + f(n)
B) Linear search problems
C) Sorting problems with O(n log n) complexity
D) Problems with constant space complexity
37. What does the recurrence relation T(n) = T(n-1) + O(1) typically represent?
A) An algorithm with exponential time complexity
B) An algorithm with linear time complexity
C) An algorithm with logarithmic time complexity
D) An algorithm with constant time complexity
38. Consider a loop that iterates 'n' times, and inside the loop, an operation takes O(n) time. What is the overall time complexity?
A) O(n)
B) O(n^2)
C) O(log n)
D) O(n log n)
39. What is the space complexity of a recursive function that has a maximum recursion depth of 'd' and each call uses constant space?
A) O(1)
B) O(d)
C) O(n)
D) O(d^2)
40. What is the time complexity of binary search on a sorted array?
A) O(n)
B) O(log n)
C) O(1)
D) O(n^2)
41. What is the time complexity of searching for an element in an unsorted array using linear search?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
42. What is the time complexity of accessing an element in an array by its index?
A) O(n)
B) O(log n)
C) O(1)
D) O(n^2)
43. Which of the following is NOT an example of an asymptotic notation?
A) O(log n)
B) O(n)
C) O(n!)
D) O(n + k)
44. What is the space complexity of an algorithm?
A) The total memory required by the algorithm
B) The maximum memory required by the algorithm at any point during its execution
C) The memory required by the input data
D) The memory required by the output data
45. Consider an algorithm with a time complexity of O(n^2). If the input size doubles, how does the execution time approximately change?
A) It doubles
B) It quadruples
C) It remains the same
D) It halves
46. Which asymptotic notation is typically used to express the worst-case time complexity?
A) Big Omega (Ω)
B) Big Theta (Θ)
C) Big O (O)
D) Little omega (ω)
47. Theta notation (Θ) provides:
A) An upper bound on the growth rate
B) A lower bound on the growth rate
C) A tight bound on the growth rate
D) An average bound on the growth rate
48. Which of the following represents the best-case time complexity?
A) Big Omega (Ω)
B) Big Theta (Θ)
C) Big O (O)
D) Little o (o)
49. What does Big O notation primarily describe?
A) The exact execution time of an algorithm
B) The minimum possible execution time of an algorithm
C) The upper bound of an algorithm's execution time or space usage
D) The average execution time of an algorithm
All Question Banks
E-Book Performance analysis: time and space complexity, asymptotic notation and recurrence relations. One Line Questions Performance analysis: time and space complexity, asymptotic notation and recurrence relations. Online Test Performance analysis: time and space complexity, asymptotic notation and recurrence relations.