Tag: running time of algorithm

Quizzes (0) Questions (2)

Questions Related to running time of algorithm

Multiple choice running time of algorithm

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. A(n)= Ω W(n) B. A(n)= O W(n) C. A(n)= Ѳ W(n) D. A(n)= o W(n)

  1. A(n) = $\omega$ W(n)

  2. A(n) = $O$ W(n)

  3. A(n) = $\theta$ W(n)

  4. A(n) = o W(n)
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

By definition, the worst-case running time W(n) is the upper bound for any input, including the average case. Therefore, A(n) is always O(W(n)).

Multiple choice running time of algorithm

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?

  1. A(n) = $\Omega$ W(n)

  2. A(n) = $O$ W(n)

  3. A(n) = $\Theta$ W(n)

  4. A(n) = o W(n)
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Average-case running time $A(n)$ is bounded above by the worst-case running time $W(n)$ for all inputs of size $n$, because the average value of a set cannot exceed its maximum. Therefore, $A(n) = O(W(n))$ always holds. The other options are false because the average case can be asymptotically strictly smaller than the worst case.