searching and sorting

Which of the following is correct recurrence for worst case of Binary Search?

• T(n) = 2T(n / 2) + O(1) and T(1) = T(0) = O(1)

• T(n) = T(n - 1) + O(1) and T(1) = T(0) = O(1)

• T(n) = T(n / 2) + O(1) and T(1) = T(0) = O(1)

• T(n) = T(n - 2) + O(1) and T(1) = T(0) = O(1)

Given a sorted array of integers, what can be the minimum worst-case time complexity to find ceiling of a number x in given array? The ceiling of an element x is the smallest element present in array which is greater than or equal to x. Ceiling is not present if x is greater than the maximum element present in array. For example, if the given array is { 12, 67 ,90,100,300,399} and x = 95 then the output should be 100.

• O (loglogn)

• O(n)

• O(log(n))

• O( log(n) * log(n))

The increasing order of performance of the searching algorithms are:

• linear search < jump search < binary search

• linear search > jump search < binary search

• linear search < jump search > binary search

• linear search > jump search > binary search

The recurrence relation that arises in relation with the complexity of binary search is:

• T(n) = 2T(n / 2) + k

• T(n) = T(n / 2) + k

• T(n) = T(n / 2)+ log(n)

• T(n) = T(n / 2) + n

Consider the following program that attempts to locate an element x in a sorted array a[] using binary search. Assume N>1. The program is erroneous. Under what conditions does the program fail?

• x is the last element of the array a

• x is greater than all elements of the array

• Both of the Above

• x is less than the last element of the array a[]

Question:

Given an array A of size N, what does the prefix sum array P represent?

Prefix sum is a technique used to compute the sum of all elements in an array from the beginning to a given index. The prefix sum array P is an array such that P[i] represents the sum of all elements in A from index 0 to i. This technique is useful in solving problems that involve range sum queries, where the goal is to find the sum of all elements in an array within a given range.

• The sum of all elements in A from index 0 to i, for each i from 0 to N-1

• The maximum element in A from index 0 to i, for each i from 0 to N-1

• The minimum element in A from index 0 to i, for each i from 0 to N-1

• The product of all elements in A from index 0 to i, for each i from 0 to N-1

Given an array A of size N, what does the prefix sum array P represent, where P[i] is computed as the sum of all elements in A from index 0 to i, modulo a prime number M?

• The number of pairs of indices (j, k) such that j < k <= i and A[j] = A[k]

• The sum of all elements in A from index 0 to i, modulo M, plus the number of prime factors of i+1

• The product of all elements in A from index 0 to i, modulo M, raised to the power of the number of distinct elements in A[0..i]

• The sum of all elements in A from index 0 to i, modulo M, minus the sum of all elements in A from index i+1 to N-1, modulo M

Question:

Given an array A of size N, containing integers up to 10^6, and a prime number M, compute the prefix sum array P such that P[i] represents the sum of all .

• The prefix sum array P cannot be computed in better than O(N^3) time, due to the need to iterate through all pairs of indices in the array A.

• The prefix sum array P can be computed in O(N log N) time using a single pass through the array A, without the need for the Sieve of Eratosthenes.

• The prefix sum array P can be computed in O(N^2) time using a nested loop approach, where the outer loop iterates through the array A and the inner loop computes the sum of all elements up to the current index.

• The prefix sum array P can be computed in O(N log log N) time using the Sieve of Eratosthenes to precompute the prime factors, and then iterating through the array A to compute the prefix sums modulo M.

What is the time complexity of the Sieve of Eratosthenes algorithm to find all prime numbers up to a given integer N?

• O(N log log N)

• O(N log N)

• O(N^2)

• O(2^N)

What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?

• Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)

• Recurrence is T(n) = T(n-1)+ O(n) and time complexity is O(n^2)

• Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nlogn)

• Recurrence is T(n) = T(n/10)+T(9n/10)+ O(n) and time complexity is O(nlogn)