The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

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

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

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

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 488
- Exam Queries 436
- Tier 1 Placement Questions 18
- Job Queries 56
- Projects 9

36,204 questions

43,662 answers

124,118 comments

42,949 users