GATE CSE 2012 | Question: 18

Question

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. $A(n) = \Omega (W(n))$
• B. $A(n) = \Theta (W(n))$
• C. $A(n) = \text{O} (W(n))$
• D. $A(n) = \text{o} (W(n))$

Comments

As arjun sir explained dats the reason c is the answer

---

Answer will be C

---

Average case of quick sort is $O(nlogn)$ and worst case is $O(n^2)$.
$$Best Case \leq AvgCase \leq WorstCase$$
Hence, (C) is the correct option.

---

is this always holds true?

BC<=Avg Case<=WC

Answer 1

Worst case complexity can never be lower than the average case complexity, but it can be higher. So, $(C)$ is the answer.
$A(n) = O(W(n))$.

Comments

O(W(n)) is tightest upper bound in worst case. Worst case tightest upper bound is average case. right?

---

what does B option mean?

---

B means both have the same asymptotic growth rate.

---

where can I find more ques of this type for practice?

---

what does small 0 denote????

---

'o'(small Oh) denotes an upper bound which is not asymptotically tight.

---

Sir can u tell me wat is wrong with option D ??

---

sir we use average case only when both worst case and best case are equal .. so in this case even option 2 must be right

---

@Puja D option tells about small-o, which requires strictly lower time complexity. Say for merge sort, D is false as Average and Worst case complexities are the same.

@Venkat "=" in the case of Asymptotic notations are not the usual "equal to". You should see this portion from Cormen - just 2-3 pages.

---

yes sir i understood it with an example average case running time for randomized quick sort is O(nlogn) but the worst case is O(n^2) so the average case is made through approximation of all the possible input sequences it doesnt mean that thetha notation is used for average case theta gives a tight bound for running time when the function is same for all the input sequences theta notation is used for describing such functions ... as i understood correct me if i am wrong @Arjun sir i went through coremen

---

yes @Venkat you are correct.

Comman mistake   :thinking  O is only for "worst", omega for "best case" and theta for "average case".

Not to be confused with worst, best and average cases analysis: all three (Omega, O, Theta) notation are not related to the best, worst and average cases analysis of algorithms. Each one of these can be applied to each analysis.

---

for eg:

---

Thanks for this statement. Really helped in clearing my concept.

---

I am not able to interpret the options properly. 

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

Says, W(n) is acting as Upper Bound for A(n), right? 

---

@kirtipurohit Yes, W(n) is acting as an upper bound for A(n) because the time for Average case can never exceed the time for Worst case. Also note that W(n) > A(n) and NOT  W(n) > A(n) because for some algorithms (for eg in mergesort) the time for Worst case and the time for Average case can be same ,i.e, W(n) = A(n). So option D is false and option C is the correct answer.

---

tel me know why option d is wrong

---

@gateranker

When we say compare function in small o  asymptotically then one function is strictly greater than the other for some values of c and n0. 

For this question 

Last option says average case = o( worst case)

Means average case has strictly lower running time than of worst case.

But when average case becomes worst case then this option fails. Therefore big o is more suitable. As Arjun sir said one example for this is Merge sort where average, best and worst case time complexity are all same. 

---

yeah same doubt came thanks for clarifying @Tushar Rana

---

qn says always .

Answer 2

Let F(n)=A(n) , G(n)=W(n)

Rule :- For Omega :-   F(n)>=cG(n)

Option A -  A(n)=Ω(W(n))   it means A(n)>=cW(n) , which is false becoz Worst case time  can not be less than avg case time.

Rule :-  For Theta :-     c1G(n) <= F(n) <= c2G(n)

Option B -  A(n)=Θ(W(n))  it means c1W(n)<=A(n)<=c2W(n) , Which can not be always true. (i.e it is false due to Bold markd line.. )

Rule :- For Big Oh :- F(n)<=cG(n)

option C-  A(n)=O(W(n)) it means A(n)<=cW(n) , which is always true........

options D:- I dont know..

Comments

I am not able to interpret the options properly. 

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

Says, W(n) is acting as Upper Bound for A(n), right? 

---

Wonderful explanation,  hats off

Thank you

Answer 3

if f(n) ≤ Cg(n)

then f(n) = O(g(n))

 

BestCase ≤ AvgCase≤WorstCase

so AvgCase ≤ WorstCase

AvgCase = O(WorstCase) will be always true

 

=> A(n)=O(W(n))

Answer 4

The average case time can be lesser than or even equal to the worst case.
So, A(n) would be upper bounded by W(n) and it will not be strict upper bound as it can even be same (e.g. Bubble Sort and merge sort).
A(n)=O(W(n))
Note: Option A is wrong because A(n) is not equal to Ω(w(n)) .

 

Hence it is option C

Comments

I am not able to interpret the options properly. 

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

Says, W(n) is acting as Upper Bound for A(n), right? 

---

@kirtipurohit

Take an example of quick sort

worst case W(n) = n$^2$ (when elements are same or are in ascending or descending order)

average case A(n) = nlogn

nlogn is always <= n$^2$

nlogn = O(n$^2$)

Hence A(n) = O(W(n))

 

 

---

Thanks, it helped. So my statement is ultimately correct, right? 

Says, W(n) is acting as Upper Bound for A(n)

---

 

No ,

Worst case doesn’t have anything to do with upper bound.

 

reference :https://news.ycombinator.com/item?id=2322051

Answer 5

For those who confuse for why not Option D
You consider DeleteMin in a Min heap. In that Case, Bothe Avg and Worst Case are logn time
That means In some cases Avg and worst case time can be same
By the way Ans is (C) as you know it.