# Questions & Answers of Sorting

Question No. 123

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?

I. Quicksort runs in Θ($\style{font-family:'Times New Roman'}{n^2}$) time

II. Bubblesort runs in Θ($\style{font-family:'Times New Roman'}{n^2}$) time

III. Mergesort runs in Θ(n) time

IV. Insertion sort runs inΘ(n) time

Question No. 237

Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?

Question No. 6

Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?

Question No. 30

The number of elements that can be sorted in Θ(log n) time using heap sort is

Question No. 16

The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is

Question No. 18

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?

Question No. 35

The running time of an algorithm is represented by the following recurrence relation:

$T\left(n\right)=\left\{\begin{array}{ll}n& n\le 3\\ T\left(\frac{n}{3}\right)+cn& otherwise\end{array}\right\$

Which one of the following represents the time complexity of the algorithm?

Question No. 40

The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is

Question No. 74

Consider the following C functions:
int f1 (int n)
{
if (n == 0 | | n == 1)
return n;
else
return (2* f1 (n - 1) + 3 * f1 (n - 2))
}
int f2 (int n)
{
int i:
int X[N], Y[N], Z[N];
X[0] = Y[0] = Z[0] = 0;
X[1] = 1; Y[1] = 2; Z[1] = 3;
for (i = 2; i <= n; i ++) {
X[i] = Y[i ? 1] + Z[i ? 2];
Y[i] = 2 * X[i];
Z[i] = 3 * X[i];
}
return X[n];
}

The running time of f1 (n) and f2 (n) are

Question No. 75

Consider the following C functions:
int f1 (int n)
{
if (n == 0 | | n == 1)
return n;
else
return (2* f1 (n - 1) + 3 * f1 (n - 2))
}
int f2 (int n)
{
int i:
int X[N], Y[N], Z[N];
X[0] = Y[0] = Z[0] = 0;
X[1] = 1; Y[1] = 2; Z[1] = 3;
for (i = 2; i <= n; i ++) {
X[i] = Y[i ? 1] + Z[i ? 2];
Y[i] = 2 * X[i];
Z[i] = 3 * X[i];
}
return X[n];
}

f1 (8) and f2 (8) return the values

Question No. 15

Consider the following segment of C-code:

int j, n;
j = 1;
while (j <= n)
j = j*2;

The number of comparisons made in the execution of the loop for any n > 0 is:

Question No. 45

What is the time complexity of the following recursive function:

int DoSomething (int n) {
if (n <= 2)
return 1;
else
return (DoSomething (floor(sqrt(n))) + n);
}

Question No. 50

An array n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?

Question No. 51

Consider the following C code segment:

int IsPrime(n)
{
int i,n;
for(i=2;i<=sqrt(n);i++)
if(n%i == 0)
{printf(“Not Prime\n”); return 0;}
return 1;
}

Let T(n) denote the number of times the for loop is executed by the program on input n. Which of the following is TRUE?