edited by
14,227 views
42 votes
42 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))$
edited by

4 Answers

Best answer
57 votes
57 votes
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
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..

1 votes
1 votes

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

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

Answer:

Related questions

35 votes
35 votes
3 answers
1
gatecse asked Aug 5, 2014
15,481 views
The recurrence relation capturing the optimal execution time of the $Towers \ of \ Hanoi$ problem with $n$ discs is$T(n) = 2T(n − 2) + 2$$T (n) = 2T(n − 1) + n$$T (...
9 votes
9 votes
4 answers
2
gatecse asked Sep 29, 2014
2,662 views
Given the sequence of terms, $\text{AD CG FK JP}$, the next term is$\text{OV}$$\text{OW}$$\text{PV}$$\text{PW}$
13 votes
13 votes
1 answer
3
gatecse asked Sep 29, 2014
2,795 views
Which one of the following options is the closest in meaning to the word given below?Mitigate DiminishDivulgeDedicateDenote
10 votes
10 votes
2 answers
4
gatecse asked Sep 29, 2014
2,939 views
Choose the most appropriate alternative from the options given below to complete the following sentence:Despite several _________ the mission succeeded in its attempt to ...