Bissoy.com
Doctors Medicines MCQs Q&A

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?

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? Correct Answer O(n*q)

For finding the result of one query the worst case time complexity will be n. So for q queries the time complexity will be O(q*n). This can be reduced by using square root optimization.

Related Questions

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?
Consider the following two tables and four queries in SQL. Book (isbn, bname), Stock (isbn, copies) Query 1: SELECT B.isbn, S.copies FROM Book B INNER JOIN Stock S ON B.isbn = S.isbn;   Query 2: SELECT B.isbn, S.copies FROM Book B LEFT OUTER JOIN Stock S ON B.isbn = S.isbn; Query 3: SELECT B.isbn, S.copies FROM Book B RIGHT OUTER JOIN Stock S ON B.isbn = S.isbn;   Query 4: SELECT B.isbn, S.copies FROM Book B FULL OUTER JOIN Stock S ON B.isbn = S.isbn;   Which one of the queries above is certain to have an output that is a superset of the outputs of the other three queries?
A teacher asked the class to subtract 5 from 75.70% of the class said: 25. Their work was shown as: \(\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 7&5 \end{array}}\\ {\underline {\begin{array}{*{20}{c}}\ { - 5} \ \ \ &{} \end{array}} }\\ {\underline {\begin{array}{*{20}{c}} 2&5 \end{array}} } \end{array}\) Which of the following describes the most appropriate remedial action that the teacher should take to clarify this misconception?
Consider the following two C code segment. Y and X are one- and two-dimensional arrays of size n and n × n respectively, where 2 ≤ n ≤ 10. Assume that in both code segments, elements of y are initialized to 0 and each element X[i] [j] of array X is initialized to i + j. Further assume that when stored in main memory all elements of x are in same main memory page frame. Code segment 1:                 //initialize elements of y to 0                 //initialize elements X[i] [j] of X to i+j                       for (i = 0; i < n; i++)                                 Y[i] += X[0] [i]; Code Segment 2:                 //initialize elements of Y to 0                 //initialize elements X[i] [j] of X to i+j                        for (i = 0; i < n; i++)                                 Y[i] += X[i] [0]; Which of the following statements is/are correct? S1: Final contents of array Y will be same in both code segments S2: Elements of array X accessed inside the for loop shown in code segment 1 are contiguous in main memory S3: Elements of array X accessed inside the for loop shown in code segment 2 are contiguous in main memory
The worst case time complexity of insertion sort is O(n2). What will be the worst case time complexity of insertion sort if the correct position for inserting element is calculated using binary search?
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?
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?
Point out the correct statement. * executes a Hive query and prints results to standard output b) executes a Hive query and prints results to standard output c) executes a Hive query and prints results to standard output d) All of the mentioned
A class III mathematics teacher gave the following questions to her students:  \(\begin{equation} \frac{ \begin{array}[b]{r} 256 \\ + 173 \end{array} }{ } \end{equation}\) \(\begin{equation} \frac{ \begin{array}[b]{r} 28 \\ + 32 \end{array} }{ } \end{equation}\) \(\begin{equation} \frac{ \begin{array}[b]{r} 129 \\ + 76 \end{array} }{ } \end{equation}\) Later she asks the students to solve a worksheet that has similar questions. Which of the following statements is appropriate for the given situation?
A material is loaded elastically under plane stress condition given by the following tensor:
\[\left[ {\begin{array}{*{20}{c}} 1 \\ 0 \end{array}\begin{array}{*{20}{c}} 2 \\ 1 \end{array}\begin{array}{*{20}{c}} 0 \\ 0 \end{array}} \right