in Algorithms edited by
11,557 views
37 votes
37 votes

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?

  1. $A(n) = \Omega (W(n))$
  2. $A(n) = \Theta (W(n))$
  3. $A(n) = \text{O} (W(n))$
  4. $A(n) = \text{o} (W(n))$
in Algorithms edited by
by
11.6k views

4 Comments

As arjun sir explained dats the reason c is the answer
0
0
Answer will be C
3
3

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.

13
13
is this always holds true?

BC<=Avg Case<=WC
2
2

4 Answers

51 votes
51 votes
Best answer
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))$.
edited by
by

4 Comments

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:

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

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? 

0
0
17 votes
17 votes

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..

by

1 comment

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? 

0
0
1 vote
1 vote

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))

by
0 votes
0 votes

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

4 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? 

1
1

@

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))

 

 

1
1

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

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

1
1

 

No ,

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

 

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

0
0
Answer:

Related questions