## 4 Answers

### 13 Comments

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

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:

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

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

No ,

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

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