Which of the following statements is true about Big-O notation?

Asked In: BPSC TRE 3.0

Options

  • A. It represents the lower bound of an algorithm’s runtime.
  • B. It represents the upper bound of an algorithm’s runtime
  • C. It represents the average runtime of an algorithm.
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

B. It represents the upper bound of an algorithm’s runtime

Detailed Explanation

Big-O notation describes an asymptotic upper bound on the growth of an algorithm’s running time or another resource as input size increases. For example, an O(N2) algorithm grows no faster than a constant multiple of N2 asymptotically. Big-Ω represents a lower bound, while Big-Θ represents a tight asymptotic bound. Big-O itself does not specifically mean average-case complexity.

← Previous Next →

Attempt Quiz Now:

BPSC TRE 4 DSA Practice set 1

Feature Posts