The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
1.8k views

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))$
asked in Algorithms by Boss (17.8k points)
retagged by | 1.8k views
0
As arjun sir explained dats the reason c is the answer
+1
Answer will be C
+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.

4 Answers

+31 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)) $$

answered by Veteran (339k points)
edited by
+1
O(W(n)) is tightest upper bound in worst case. Worst case tightest upper bound is average case. right?
0
what does B option mean?
+1
B means both have the same asymptotic growth rate.
0
where can I find more ques of this type for practice?
+1
what does small 0 denote????
+1
'o'(small Oh) denotes an upper bound which is not asymptotically tight.
0
Sir can u tell me wat is wrong with option D ??
0
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
+10
@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.
0
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
+3

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:

+1 vote

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

 

answered by Active (1.2k points)
–1 vote
option C
answered by (17 points)
0
Explain otherwise upvote correct answer ...
–1 vote
Option C is correct.
answered by Active (2.3k points)
reshown by
0
Explain otherwise upvote correct answer ...


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,780 questions
41,758 answers
118,934 comments
41,400 users