Question 8829 – Theory-of-Computation
May 4, 2024Question 10529 – Algorithms
May 4, 2024Question 8822 – Algorithms
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?
Correct Answer: C
Question 26 Explanation:
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)) .
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)) .
A(n) = Ω (W(n))
A(n) = Θ (W(n))
A(n) = O (W(n))
A(n) = o (W(n))
Subscribe
Login
0 Comments