Performance Analysis - time and space complexities, asymptotic notation, recurrence relations - Question Bank

1. Which of the following is an example of an algorithm with O(n log n) time complexity?
A) Bubble Sort
B) Insertion Sort
C) Merge Sort
D) Linear Search
2. Which of the following is an example of an algorithm with O(1) time complexity?
A) Accessing an element in an array by its index.
B) Searching for an element in a sorted array.
C) Iterating through all elements of a list.
D) Sorting a list of elements.
3. What does T(n) = Θ(n^2) imply about the algorithm's runtime?
A) The runtime is always less than or equal to c1*n^2 and greater than or equal to c2*n^2 for some constants c1 and c2.
B) The runtime is always less than or equal to c*n^2 for some constant c.
C) The runtime is always greater than or equal to c*n^2 for some constant c.
D) The runtime is exactly proportional to n^2 for all n.
4. What does T(n) = Ω(n^2) imply about the algorithm's runtime?
A) The runtime is always less than or equal to c*n^2 for some constant c.
B) The runtime is always greater than or equal to c*n^2 for some constant c.
C) The runtime is exactly proportional to n^2.
D) The runtime is greater than c*n^2 for all n.
5. What does T(n) = O(n^2) imply about the algorithm's runtime?
A) The runtime is always less than or equal to c*n^2 for some constant c.
B) The runtime is always greater than or equal to c*n^2 for some constant c.
C) The runtime is exactly proportional to n^2.
D) The runtime is less than c*n^2 for all n.
6. Which of the following is NOT a standard asymptotic notation used in performance analysis?
A) Big O (O)
B) Big Omega (Ω)
C) Big Theta (Θ)
D) Big Sigma (Σ)
7. The Master Theorem can be used to solve recurrence relations of the form T(n) = aT(n/b) + f(n) where a >= 1, b > 1. Which condition corresponds to the solution T(n) = Θ(n^(log_b a))?
A) f(n) = O(n^(log_b a - ε)) for some ε > 0
B) f(n) = Θ(n^(log_b a))
C) f(n) = Ω(n^(log_b a + ε)) for some ε > 0 and a*f(n/b) <= c*f(n) for some c < 1
D) f(n) = O(n^(log_b a + ε)) for some ε > 0
8. The Master Theorem can be used to solve recurrence relations of the form T(n) = aT(n/b) + f(n) where a >= 1, b > 1. Which condition corresponds to the solution T(n) = Θ(f(n))?
A) f(n) = O(n^(log_b a - ε)) for some ε > 0
B) f(n) = Θ(n^(log_b a))
C) f(n) = Ω(n^(log_b a + ε)) for some ε > 0 and a*f(n/b) <= c*f(n) for some c < 1
D) f(n) = O(n^(log_b a + ε)) for some ε > 0
9. The Master Theorem can be used to solve recurrence relations of the form T(n) = aT(n/b) + f(n) where a >= 1, b > 1. Which condition corresponds to the solution T(n) = Θ(n^log_b a)?
A) f(n) = O(n^(log_b a - ε)) for some ε > 0
B) f(n) = Θ(n^(log_b a))
C) f(n) = Ω(n^(log_b a + ε)) for some ε > 0 and a*f(n/b) <= c*f(n) for some c < 1
D) f(n) = O(n^(log_b a + ε)) for some ε > 0
10. Consider the recurrence relation T(n) = 2T(n/2) + n^2. What is its solution using the Master Theorem?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(n^3)
11. Consider the recurrence relation T(n) = 4T(n/2) + n. What is its solution using the Master Theorem?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(n^3)
12. Consider the recurrence relation T(n) = T(n/2) + c. What is its solution?
A) O(n)
B) O(n log n)
C) O(log n)
D) O(1)
13. Consider the recurrence relation T(n) = 2T(n/2) + n. What is its solution using the Master Theorem (assuming n is a power of 2)?
A) O(log n)
B) O(n)
C) O(n log n)
D) O(n^2)
14. Which of the following is a typical base case for a recurrence relation?
A) T(n) = T(n/2) + c
B) T(n) = 2T(n/2) + n
C) T(1) = c
D) T(n) = T(n-1) + n
15. What is the primary use of recurrence relations in algorithm analysis?
A) To determine the exact execution time in milliseconds.
B) To describe and solve the time complexity of recursive algorithms.
C) To visualize the algorithm's data flow.
D) To optimize memory usage.
16. If f(n) = 3n^2 + 2n + 1 and g(n) = n^2, then f(n) is Θ(g(n)). Is this statement true or false?
A) True
B) False
C) Cannot be determined
D) Depends on the input
17. If f(n) = 2n + 5 and g(n) = n, then f(n) is Θ(g(n)). Is this statement true or false?
A) True
B) False
C) Cannot be determined
D) Depends on the input
18. If f(n) = n and g(n) = n^2, then f(n) is O(g(n)). Is this statement true or false?
A) True
B) False
C) Cannot be determined
D) Depends on the input
19. If f(n) = n^2 and g(n) = n, then f(n) is Ω(g(n)). Is this statement true or false?
A) True
B) False
C) Cannot be determined
D) Depends on the input
20. What does 'Little omega' (ω) notation represent?
A) A lower bound
B) A tight bound
C) A strict upper bound (function grows strictly slower)
D) A strict lower bound (function grows strictly faster)
21. What does 'Little o' (o) notation represent?
A) A lower bound
B) A tight bound
C) A strict upper bound (function grows strictly slower)
D) A strict lower bound (function grows strictly faster)
22. What is the space complexity of an algorithm that uses an auxiliary array of size n?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
23. What is the space complexity of an algorithm that sorts an array of n elements in-place (e.g., Heap Sort)?
A) O(n)
B) O(log n)
C) O(1)
D) O(n log n)
24. What is the space complexity of a recursive function that has a maximum recursion depth of k?
A) O(1)
B) O(k)
C) O(n)
D) O(k^2)
25. Consider the following C code snippet: `int i = n; while (i > 0) { i /= 2; }`. What is its time complexity?
A) O(n)
B) O(n^2)
C) O(log n)
D) O(1)
26. Consider the following C code snippet: `int i = 1; while (i < n) { i *= 2; }`. What is its time complexity?
A) O(n)
B) O(n^2)
C) O(log n)
D) O(1)
27. Consider the following C code snippet: `for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { /* constant time operation */ } }`. What is its time complexity?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(2^n)
28. What is the Big O complexity of linear search on an unsorted array of n elements?
A) O(log n)
B) O(n)
C) O(n log n)
D) O(n^2)
29. What is the Big O complexity of binary search on a sorted array of n elements?
A) O(n)
B) O(n log n)
C) O(log n)
D) O(1)
30. What is the Big O complexity of an algorithm that iterates through a list of n elements using nested loops, where each loop runs n times?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(2^n)
31. What is the Big O complexity of an algorithm that iterates through a list of n elements once?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
32. Which growth rate is faster: O(log n) or O(n)?
A) O(log n)
B) O(n)
C) They grow at the same rate.
D) Depends on the base of the logarithm.
33. Which growth rate is faster: O(n^2) or O(n log n)?
A) O(n log n)
B) O(n^2)
C) They grow at the same rate.
D) Cannot be determined without input size.
34. If T(n) is Θ(f(n)), which of the following is true?
A) T(n) is O(f(n)) and T(n) is Ω(f(n))
B) T(n) is only O(f(n))
C) T(n) is only Ω(f(n))
D) T(n) is neither O(f(n)) nor Ω(f(n))
35. What does Big Theta (Θ) notation signify?
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.
36. If an algorithm's runtime is T(n) = n log n + 5n, what is its Big O complexity?
A) O(n)
B) O(log n)
C) O(n log n)
D) O(n^2)
37. If an algorithm's runtime is T(n) = 2^n + n^3, what is its Big O complexity?
A) O(n^3)
B) O(2^n)
C) O(n log n)
D) O(n)
38. If an algorithm's runtime is T(n) = 100, what is its Big O complexity?
A) O(n)
B) O(log n)
C) O(n^2)
D) O(1)
39. If an algorithm's runtime is T(n) = 5n + 20, what is its Big O complexity?
A) O(n^2)
B) O(log n)
C) O(n)
D) O(1)
40. If an algorithm's runtime is T(n) = 3n^2 + 5n + 10, what is its Big O complexity?
A) O(n)
B) O(n^2)
C) O(log n)
D) O(n^3)
41. Which asymptotic notation provides a tight bound (both upper and lower) on the growth rate of a function?
A) Big O (O)
B) Big Omega (Ω)
C) Little o (o)
D) Big Theta (Θ)
42. Which asymptotic notation provides a lower bound on the growth rate of a function?
A) Big O (O)
B) Big Omega (Ω)
C) Big Theta (Θ)
D) Little omega (ω)
43. Which asymptotic notation provides an upper bound on the growth rate of a function?
A) Big Omega (Ω)
B) Big Theta (Θ)
C) Little o (o)
D) Big O (O)
44. What does 'average-case' complexity refer to in algorithm analysis?
A) The maximum time or space required for any input.
B) The minimum time or space required for any input.
C) The time or space required for a specific, typical input.
D) The expected time or space required over all possible inputs.
45. What does 'worst-case' complexity refer to in algorithm analysis?
A) The minimum time or space required for any input.
B) The average time or space required for all possible inputs.
C) The maximum time or space required for any input.
D) The time or space required for a specific, typical input.
46. What does 'best-case' complexity refer to in algorithm analysis?
A) The maximum time or space required for any input.
B) The minimum time or space required for any input.
C) The average time or space required for all possible inputs.
D) The time or space required for a specific, typical input.
47. Which measure quantifies the amount of time an algorithm takes to run?
A) Space complexity
B) Execution speed
C) Time complexity
D) Memory usage
48. Which measure quantifies the amount of memory an algorithm uses?
A) Time complexity
B) Space complexity
C) Execution time
D) Algorithmic efficiency
49. What is the primary goal of performance analysis in algorithms?
A) To make the algorithm visually appealing.
B) To determine the efficiency of an algorithm in terms of time and space.
C) To guarantee the algorithm always produces a correct output.
D) To implement the algorithm on the smallest possible hardware.
All Question Banks
E-Book Performance Analysis - time and space complexities, asymptotic notation, recurrence relations One Line Questions Performance Analysis - time and space complexities, asymptotic notation, recurrence relations Online Test Performance Analysis - time and space complexities, asymptotic notation, recurrence relations