The Gateway to Computer Science Excellence

+29 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**?

- $A(n) = \Omega (W(n))$
- $A(n) = \Theta (W(n))$
- $A(n) = \text{O} (W(n))$
- $A(n) = \text{o} (W(n))$

+42 votes

Best answer

+1

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

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

+14

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

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

+1

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

+9

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

52,345 questions

60,470 answers

201,796 comments

95,272 users