# GATE Questions & Answers of Asymptotic Worst Case Time and Space Complexity

## What is Asymptotic Worst Case Time and Space Complexity ?

In computer science, best, worst, and average cases of a given algorithm express what the resource usage is at least, at most and on average, respectively. Usually the resource being considered is running time, i.e. time complexity, but it could also

## What is the Weightage of Asymptotic Worst Case Time and Space Complexity in GATE Exam?

Total 16 Questions have been asked from Asymptotic Worst Case Time and Space Complexity topic of Algorithms subject in previous GATE papers. Average marks 1.62.

There are n unsorted arrays: A1, A2, …, An. Assume that n is odd. Each of A1, A2, …, An contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A1, A2, …, An is

##### Show Answer

Consider the following function from positive integers to real numbers:

$\style{font-family:'Times New Roman'}{10,\;\sqrt n,\;n,\;\log_2n,\;\frac{100}n.}$

The CORRECT arrangement of the above functions in increasing  order of asymptotic complexity is:

##### Show Answer

Match the algorithms with their time complexities:

 Algorithm Time complexity (P) Towers of Hanoi with n disks (i)$\style{font-family:'Times New Roman'}{\Theta(n^2)}$ (Q) Binary search given n stored numbers (ii)$\style{font-family:'Times New Roman'}{\Theta(n\;\log\;n)}$ (R) Heap sort given n numbers at the worst case (iii)$\style{font-family:'Times New Roman'}{\Theta(2^n)}$ (S) Addition of two n$\style{font-family:'Times New Roman'}\times$n matrices (iv)$\style{font-family:'Times New Roman'}{\Theta(\log\;n)}$

##### Show Answer

Consider the following C function

int. fun(int.n) {
int i, j;
for(i = 1; i<= n; i++) {
for(j=1; j<n; j += i) {
printf(" %d %d",i,j);
}
}
}
Time complexity of fun in terms of $\theta$ notation is

##### Show Answer

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

##### Show Answer

Consider the following C program segment.

while(first <= last)
{
if(array[middle] < search)
first = middle + 1;
else if (array[middle] = = search)
found = TRUE;
else last = middle – 1;
middle = (first + last)/2;
}
if (first > last) notPresent = TRUE;

The cyclomatic complexity of the program segment is ______.

##### Show Answer

An   algorithm   performs   (log N)1/2   find   operations,  N insert   operations,   (log N)1/2  delete operations, and (log N)1/2 decrease-key operations on a set of data items with keys drawn form a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best asymptotic complexity considering all the operations?

##### Show Answer

Consider the following C function.
int fun1 (int n){
int i, j, k, p, q = 0;
for (i = 1; i < n; ++i) {
p = 0;
for(j = n; j > 1; j = j/2)
++p;
for(k =1; k < p; k = k*2)
++q;
}
return q;
}

Which one of the following most closely approximates the return value of the function fun1?

##### Show Answer

An unordered list contains $n$ distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is

##### Show Answer

Suppose $c=\left\langle c\left[0\right],\;...,\;c\left[k-1\right]\right\rangle$ is an array of lengt $k$, where all the entries are from the set {0, 1}. For any positive integers a and n, consider the following pseudocode.

DOSOMETHING (c, a, n)
z ← 1
for i ← 0 to k – 1
do zz2mod n
if c[i] = 1
then z ← (z $\times$ a) mod n
return z

If $k=4,\;c=\left\langle1,\;0,\;1,\;1\right\rangle a=2$ and n = 8, then the output of DOSOMETHING (c, a, n) is _________.

##### Show Answer

Let (n) = n and g(n) = n(1+sin n), where n is a positive integer. Which of the following statements is/are correct?

I.  (n) = O(g(n))
II. (n) = $\Omega$(g(n))

##### Show Answer

Consider the following function:
int unknown(int n){
int i, j, k=0;
for (i=n/2; i<=n; i++)
for (j=2; j<=n; j=j*2)
k = k + n/2;
return (k);
}

The return value of the function is

##### Show Answer

Which of the given options provides the increasing order of asymptotic complexity of functions ${f}_{1},{f}_{2,}{f}_{3}$, and ${f}_{4}$?

${f}_{1}\left(n\right)={2}^{n}$    ${f}_{2}\left(n\right)={n}^{3}{2}}$  ${f}_{3}\left(n\right)=n{\mathrm{log}}_{2}n$  ${f}_{4}\left(n\right)={n}^{{\mathrm{log}}_{2}n}$

##### Show Answer

Two alternative packages A and B are available for processing a database having 10k records. Package A requires 0.0001n2 time units and package B requires ${10}_{n}{\mathrm{log}}_{10}n$ time units to process n records. What is the smallest value of k for which package B will be preferred over A?

##### Show Answer

What is the number of swaps required to sort n elements using selection sort, in the worst case?

##### Show Answer

Consider the following functions:
f(n) = 2n
g(n) = n!
h(n) = nlogn

Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?