...
Question 8829 – Theory-of-Computation
May 4, 2024
Question 10529 – Algorithms
May 4, 2024
Question 8829 – Theory-of-Computation
May 4, 2024
Question 10529 – Algorithms
May 4, 2024

Question 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)) .
A
A(n) = Ω (W(n))
B
A(n) = Θ (W(n))
C
A(n) = O (W(n))
D
A(n) = o (W(n))
0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x
error: Alert: Content selection is disabled!!