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

The algorithm uses characteristic arrays $x$ and $y$ to represent sets $X$ and $Y$ respectively, where a value of $1$ at index $i$ indicates that $i$ is a member of the set, and $0$ indicates it is not.

For each index $i$, the algorithm computes:

$$\text{z}[i] = (x[i] \land \neg y[i]) \lor (\neg x[i] \land y[i])$$

Let us translate this logical expression into set operations:

• $x[i] \land \neg y[i]$ is true if and only if $i \in X$ and $i \notin Y$. This corresponds to the set difference: $X - Y$.
• $\neg x[i] \land y[i]$ is true if and only if $i \notin X$ and $i \in Y$. This corresponds to the set difference: $Y - X$.
• The logical OR ($\lor$) operator combines these two conditions, which corresponds to the set union ($\cup$).

Thus, $z[i] = 1$ if and only if:

$$i \in (X - Y) \cup (Y - X)$$

This expression represents the symmetric difference of the two sets, $X \Delta Y$. Therefore, the set $Z$ computed by the algorithm is $(X - Y) \cup (Y - X)$.