Square Root Decomposition MCQ

Test your knowledge with important Square Root Decomposition MCQ and their applications. These MCQs are beneficial for competitive exams too. Explore 30 + more Square Root Decomposition MCQs at Bissoy

• What will be the time complexity of the code to find a minimum element from an array of size n and uses square root decomposition(exclude pre processing time)?
  ক

  O(√n)

  খ

  O(n)

  গ

  O(1)

  ঘ

  O(n2)
• Mo’s algorithm can only be used for problems where the query can be calculated from the result of the previous query.
  ক

  true

  খ

  false
• What will be the worst case time complexity of code to find sum in given query range (l,r) in an array of size n with q number of such queries when we apply MO’s algorithm?
  ক

  O(n*q)

  খ

  O(n)

  গ

  O((q+n)√n)

  ঘ

  O(q*√n)
• What will be the worst case time complexity of code to find sum in given query range (l,r) in an array of size n with q number of such queries?
  ক

  O(n)

  খ

  O(q)

  গ

  O(n*q)

  ঘ

  O(n+q)
• Square root decomposition technique is only applicable when the number of indices in an array is a perfect square.
  ক

  true

  খ

  false
• What will be the time complexity of update query operation in an array of size n when we use square root optimization?
  ক

  O(√n)

  খ

  O(n)

  গ

  O(1)

  ঘ

  O(n2)
• Total how many iterations are required to find the sum of elements in a given range of (l,r) in an array of size n when we use square root optimization?
  ক

  √n

  খ

  2*√n

  গ

  3*√n

  ঘ

  n*√n
• What will be the worst case time complexity of finding the sum of elements in a given range of (l,r) in an array of size n when we use square root optimization?
  ক

  O(n)

  খ

  O(l+r)

  গ

  O(√n)

  ঘ

  O(r-l)
• What will be the worst case time complexity of finding the sum of elements in a given range of (l,r) in an array of size n?
  ক

  O(n)

  খ

  O(l+r)

  গ

  O(l-r)

  ঘ

  O(r-l)
• By what factor time complexity is reduced when we apply square root decomposition to a code?
  ক

  n

  খ

  √n

  গ

  n2

  ঘ

  n-1/2
• What is the purpose of using square root decomposition?
  ক

  to reduce the time complexity of a code

  খ

  to increase the space complexity of a code

  গ

  to reduce the space complexity of a code

  ঘ

  to reduce the space and time complexity of a code