UGC NET CSE | October 2020 | Part 2 | Question: 52

Question

The running time of an algorithm is $O(g(n))$ if and only if

1. its worst-case running time is $O(g(n))$ and its best-case running time is $\Omega(g(n)) \cdot (O= \textit{ big }O)$
2. its worst-case running time is $\Omega (g(n))$ and its best-case running time is $O(g(n)) \cdot (O= \textit{ big }O)$
3. $O(g(n))= \Omega(g(n))(O=\textit{big } O)$
4. $O(g(n))\cap \omega(g(n))$ is non-empty set, $(o = \textit{ small } o)$

 

Comments

“The running time of an algorithm is O(g(n)”

should it be  O(g(n))  or  Θ(g(n))

and  what is the significance of  second part  best-case running time is Ω(g(n))

---

@gatecse in option (d) “  $=\cap$ “ i think need to edit .

---

Fixed now 👍

Answer 1

Option (A) Worst case of algorithm is $O(g(n))$, means that in worst case the algorithm's time complexity grows (asymptotically or for sufficiently large $n$) no faster than $g(n)$.

Best case of algorithm is $\Omega(g(n)$, means that in best case inputs, the algorithm's time complexity grows at least as fast as $g(n)$.

From these two statements we can conclude that best case time complexity of algorithm is $\Theta(g(n))$ and worst case time complexity of algorithm is $\Theta(g(n))$.

From this we can conclude that, average case time complexity will also be $\Theta(g(n))$.

Which implies algorithm's running time complexity is $\Theta(g(n))$ which in turn implies algorithm's running time complexity is $O(g(n))$.

That is, Option (A) implies running time complexity is $O(g(n))$.

But running time complexity is $O(g(n))$ does not imply Option (A).

For this counter example is Insertion sort, it's running time complexity is $O(n^2)$, worst case time complexity is $O(n^2)$ but it's best case time complexity is not $\Omega(n^2)$.

Therefore, option (A) must be False.

Comments

Option A is false as shown above. How can option A be modified to make it True? Options B,C and D are also false right?

Answer 2

1. (A only)
 for the best case, the time complexity will be minimum and would be omega(n) and for the worst case, it would be O(g(n)).

Answer 3

According to me option C is correct.

As for option A, if worst case becomes 0( g(n)) and best case becomes Ω( g(n)) then the running time becomes Θ( g(n))

as every time complexity is the upper and lower bound to itself.

 

Whereas for option C, since the upper bound and lower bound are same, it doesn’t matter if we mention the 0( g(n)) or Ω( g(n)) as both are same.

Answer 4

O(g(n)) gives the upper bound on a algorithm and Ω(g(n)) gives the lower bound. Hence Option A should be correct.