Question

Name the notation that represents the average-case complexity of an algorithm.

• A. Big O
• B. Little o
• C. Big Omega
• D. Big Theta

Hint:

Formally, $f(n) = \Theta(g(n))$ if and only if $f(n) = O(g(n))$ AND $f(n) = \Omega(g(n))$. It represents the most precise description of the algorithm's complexity.

Answer 1

The Correct Option is D

Concept: Asymptotic notations are mathematical tools used to describe the limiting behavior of a function (the algorithm's runtime).
• Big O ($O$): Provides an upper bound (Worst case).
• Big Omega ($\Omega$): Provides a lower bound (Best case).
• Big Theta ($\Theta$): Provides a tight bound (Average case).

Step 1: Defining the "Tight Bound".
Big Theta describes a function that is bounded both from above and below. If $f(n) = \Theta(g(n))$, it means the growth rate of $f(n)$ is exactly the same as $g(n)$.

Step 2: Relating to "Average Case".
Average-case complexity describes the behavior of an algorithm on "typical" inputs. We use $\Theta$ to signify that the performance is consistently centered on a specific growth rate.

Step 3: Conclusion.
While Big O is most common in industry to guarantee limits, Big Theta is the precise notation. Thus, for average-case or "exact" complexity, Big Theta is the correct answer.