GATE CS 2012 Q.18 (CS Q.18): Asymptotic Analysis and Time/Space Complexity

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?

$A(n) = \Omega(W(n))$

$A(n) = \Theta(W(n))$

$A(n) = O(W(n))$

$A(n) = o(W(n))$

Official answer and solution

Official answer: C
From: Official GATE 2012 answer key

Solution

Analyze the definitions of worst-case complexity $W(n)$ and average-case complexity $A(n)$ .

Let $I_n$ be the set of all valid inputs of size $n$ , and let $t(x)$ denote the running time of the algorithm on input $x \in I_n$ .
The worst-case running time is the maximum running time over all inputs of size $n$ :

W(n) = \max_{x \in I_n} t(x)

The average-case running time $A(n)$ is the expected running time across all inputs distributed according to probability distribution $P(x)$ :

A(n) = \sum_{x \in I_n} P(x) \cdot t(x)

Since $t(x) \le W(n)$ for every input $x \in I_n$ , and $\sum_{x \in I_n} P(x) = 1$ , we have:

A(n) \le \sum_{x \in I_n} P(x) \cdot W(n) = W(n) \cdot \sum_{x \in I_n} P(x) = W(n)

Since $A(n) \le W(n)$ for all $n$ , by definition of asymptotic upper bound, $A(n) = O(W(n))$ is always true.
Examination of other options:

In QuickSort, $A(n) = \Theta(n \log n)$ while $W(n) = \Theta(n^2)$ . Here $A(n) \ne \Omega(W(n))$ and $A(n) \ne \Theta(W(n))$ , ruling out (A) and (B).
In MergeSort, $A(n) = \Theta(n \log n)$ and $W(n) = \Theta(n \log n)$ , so $A(n) \ne o(W(n))$ , ruling out (D).

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2012 Computer Science and Information Technology (CS)
Question: 18 of 65, printed as CS Q.18
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source