Official PYQ · 2006Q53Asymptotic Worst Case Time and Space ComplexityMCQ1 mark

GATE CS 2006 Q53 — Asymptotic Worst Case Time and Space Complexity

Consider the following C-function in which $a[n]$ and $b[m]$ are two sorted integer arrays and $c[n+m]$ be another integer array,

void xyz(int a[], int b [], int c []){ 
    int i,j,k; 
    i=j=k=0; 
    while ((i<n) && (j<m)) 
        if (a[i] < b[j]) c[k++] = a[i++]; 
        else c[k++] = b[j++]; 
}

Which of the following condition(s) hold(s) after the termination of the while loop?

$j< m,k=n+j-1$ and $a[n-1]< b[j]$ if $i=n$
$i<n,k=m+i-1$ and $b[m-1]\leq a[i]$ if $j=m$

View worked solution

Answer: D

To determine which conditions hold after the termination of the while loop, we can analyze the loop variables $i$ , $j$ , and $k$ .

In every iteration of the loop, exactly one of $i$ or $j$ is incremented, and $k$ is always incremented. Since all three variables are initialized to $0$ , the loop invariant relation is:

k = i + j

Let's evaluate the two cases upon loop termination:

Case 1: $i = n$ (and $j < m$ )
Substituting $i = n$ into our invariant gives $k = n + j$ . Statement (i) claims that $k = n + j - 1$ , which is incorrect.
Case 2: $j = m$ (and $i < n$ )
Substituting $j = m$ into our invariant gives $k = m + i$ . Statement (ii) claims that $k = m + i - 1$ , which is also incorrect.

Since the relation for $k$ is incorrect in both statements, neither condition (i) nor (ii) holds true upon termination.

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

Browse this topic

More Asymptotic Worst Case Time and Space Complexity questions

GATE CS 2006 Q53 — Asymptotic Worst Case Time and Space Complexity

Related questions