Bissoy.com
Doctors Medicines MCQs Q&A

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?

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? Correct Answer 3*√n

After calculating the sum of each chunk individually we require to iterate only 3*√n times to calculate the sum in the worst case. It is because two of the √n factors consider the worst case time complexity of summing elements in the first and last block. Whereas the third √n considers the factor of summing the √n chunks.

Related Questions

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
Given below are three quantities named 1, 2 and 3. Based on the given information, you have to determine the relationship between the three quantities. You should use the given data and knowledge of Mathematics to choose between the possible answer. Quantity 1: Area of the innermost square. A square is made by joining the midpoints of a square of area 200 sq. m. The outermost square is called Square 1, The square inside it is called Square 2. The next square is made by joining midpoints of square 2 and is called Square 3. This process goes on. Square 5 is the innermost square. Quantity 2: A man starts with a speed of 10 km/hr. He increases his speed by 10 km/hr every hour at the start and drives at the same speed for that hour. If he traveled a total distance of 550 km. Find the time Quantity 3: Height of cylinder Its volume is equal to the volume of a cone whose radius is 14 cm and height is 39.3 cm. The radius of the cylinder is 14 cm
When subtracting the square root of the square root of 625 from the square root of the square root of 1296, which of the following number is square root of the difference?
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?
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?
Which of the following statements are correct? (i) All elements of an array are ints (ii) All elements of an array are floats (iii) Some elements of an array can be ints and other floats (iv) All elements of an array are chars 
Which of the following can act as possible termination conditions in K-Means?
1. For a fixed number of iterations.
2. Assignment of observations to clusters does not change between iterations. Except for cases with a bad local minimum.
3. Centroids do not change between successive iterations.
4. Terminate when RSS falls below a threshold.
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
What will be the time complexity of update query operation in an array of size n when we use square root optimization?