TRB PG Assistant - Performance Analysis - time and space complexities, asymptotic notation, recurrence relations Online Test (MCQ Quiz)

1. 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.

2. Which measure quantifies the amount of memory an algorithm uses?

A) Time complexity B) Space complexity C) Execution time D) Algorithmic efficiency

3. Which measure quantifies the amount of time an algorithm takes to run?

A) Space complexity B) Execution speed C) Time complexity D) Memory usage

4. 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.

5. 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.

6. 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.

7. 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)

8. 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 (ω)

9. 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 (Θ)

10. 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)

11. 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)

12. 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)

13. 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)

14. 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)

15. 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.

16. 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))

17. 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.

18. 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.

19. 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)

20. 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)

21. 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)

22. 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)

23. 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)

24. 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)

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. 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)

27. 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)

28. 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)

29. 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)

30. 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)

31. 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

32. 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

33. 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

34. 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

35. 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.

36. 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

37. 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)

38. 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)

39. 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)

40. 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)

41. 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

42. 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

43. 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

44. 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 (Σ)

45. 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.

46. 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.

47. 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.

48. 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.

49. 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

Performance Analysis - time and space complexities, asymptotic notation, recurrence relations - Online Test

Test Results