UGC NET - Performance analysis: time and space complexity, asymptotic notation and recurrence relations. Online Test (MCQ Quiz)

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

2. Which of the following represents the best-case time complexity?

A) Big Omega (Ω) B) Big Theta (Θ) C) Big O (O) D) Little o (o)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 quicksort in the average case?

A) O(n) B) O(n log n) C) O(n^2) D) O(log n)

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

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

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

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

31. What is the time complexity of adding two numbers?

A) O(n) B) O(log n) C) O(1) D) O(n^2)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Performance analysis: time and space complexity, asymptotic notation and recurrence relations. - Online Test

Test Results