Dark Mode On/Off

# Sorting Algorithm and Time Complexity Test 1

This Test will cover basic concepts of various sorting algorithms and time complexity of algorithms.
Q. What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?
 A. Recurrence is `T(n) = T(n-2) + O(n)` and time complexity is `O(n2)` B. Recurrence is `T(n) = T(n-1) + O(n)` and time complexity is `O(n2)` C. Recurrence is `T(n) = 2T(n/2) + O(n)` and time complexity is `O(nlogn)` D. Recurrence is `T(n) = T(n/10) + T(9n/10) + O(n)` and time complexity is `O(nlogn)`
Q. Suppose we have a `O(n)` time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort
 A. `O(n2*logn)` B. `O(n2)` C. `O(n*logn*logn)` D. `O(n*logn)`
Q. Given an unsorted array. The array has a property that every element in the array is at most `k` distance from its position in sorted array, where `k` is a positive integer smaller than the size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?
 A. Insertion Sort with time complexity `O(kn)` B. Heap Sort with time complexity `O(nLogk)` C. Quick Sort with time complexity `O(kLogk)` D. Merge Sort with time complexity `O(kLogk)`

Q. Which of the following is not true about comparison based sorting algorithms?
 A. The minimum possible time complexity of a comparison based sorting algorithm is `O(nLogn)` for a random input array. B. Any comparison based sorting algorithm can be made stable by using position as a criteria when two elements are compared. C. Counting Sort is not a comparison based sorting algorithm. D. Heap Sort is not a comparison based sorting algorithm.
Q. What is time complexity of `fun()`?
``````int fun(int n)
{
int count = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
return count;
}``````
 A. `O(n2)` B. `O(n*logn)` C. `O(n)` D. `O(n*logn*logn)`
Q. What is time complexity of `fun()`?
``````int fun(int n)
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = i; j > 0; j--)
count = count + 1;
return count;
}``````
 A. `Theta(n)` B. `Theta(n2)` C. `Theta(n*logn)` D. `Theta(n*logn*logn)`
Q. The recurrence relation capturing the optimal time of the Tower of Hanoi problem with `n` discs is __________?
 A. T(n) = 2T(n - 2) + 2 B. T(n) = 2T(n - 1) + n C. T(n) = 2T(n/2) + 1 D. T(n) = 2T(n - 1) + 1
Q. Let `W(n)` and `A(n)` denote respectively, the worst case and average case running time of an algorithm executed on an input of size `n`. Which of the following is ALWAYS TRUE?
 A. A(n) = Ω(W(n)) B. A(n) = θ(W(n)) C. A(n) = O(W(n)) D. A(n) = o(W(n))

Q. Which of the following is not O(n2)?
 A. (1510)*n + 12099 B. n1.98 C. n3 / (sqrt(n)) D. (220)*n
Q. Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4?
```f1(n) = 2n

f2(n) = n(3/2)

f3(n) = n*Logn

f4(n) = nLogn
```
 A. f3, f2, f4, f1 B. f3, f2, f1, f4 C. f2, f3, f1, f4 D. f2, f3, f4, f1
Q. Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let n = D1D2...Dm, where D1, D2 etc are digits forming the integer number. The loop invariant condition at the end of the ith iteration is:
``````rev = 0;
while (n > 0)
{
rev = rev*10 + n%10;
n = n/10;
}``````
 A. n = D1D2...D(m-i) and rev = DmD(m-1)...D(m-i+1) B. n = D(m-i+1)...Dm-1Dm and rev = D(m-1)...D2D1 C. n != rev D. n = D1D2...Dm and rev = DmD(m-1)...D2D1
Q. What is the best time complexity of Bubble Sort?
 A. N2 B. NlogN C. N D. N(logN)2

Q. What is the worst case time complexity of Insertion sort where position of the data to be inserted is calculated using Binary search?
 A. N B. NlogN C. N2 D. N(logN)2
Q. The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of:
 A. N B. N2 C. NlogN D. N(logN)2
Q. In a modified Merge sort, the input array is splitted at a position one-third of the length(`N`) of the array. What is the worst case time complexity of this merge sort?
 A. N(logN base 3) B. N(logN base 2/3) C. N(logN base 1/3) D. N(logN base 3/2)