This Test will cover basic concepts of various sorting algorithms and time complexity of algorithms.
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 QuickSortk
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?
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;
}
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;
}
n
discs is __________?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?
f1(n) = 2n f2(n) = n(3/2) f3(n) = n*Logn f4(n) = nLogn
rev = 0;
while (n > 0)
{
rev = rev*10 + n%10;
n = n/10;
}
N
) of the array. What is the worst case time complexity of this merge sort?