Question

What is the time complexity in Big-Oh notation for \[ f(n)=a_{m}n^{m}+\cdots+a_{1}n+a_{0}? \]

• A. \(O(n^2)\)
• B. \(O(n^3)\)
• C. \(O(2^n)\)
• D. \(O(n^m)\)

Hint:

For polynomial functions, Big-Oh complexity is determined by the highest power of \(n\). Example: \[ 5n^4+2n^2+10 \] has complexity \[ O(n^4). \]

Answer 1

The Correct Option is D

Concept: Big-Oh notation describes the asymptotic growth rate of a function. For a polynomial function, \[ f(n)=a_{m}n^{m}+a_{m-1}n^{m-1}+\cdots+a_{1}n+a_{0}, \] the highest degree term dominates the growth when \(n\) becomes very large. Therefore, lower-order terms and constant coefficients become insignificant in asymptotic analysis.

Step 1: Identify the highest power of \(n\).
The given polynomial is \[ f(n)=a_{m}n^{m}+a_{m-1}n^{m-1}+\cdots+a_{1}n+a_{0}. \] The highest degree term is \[ a_{m}n^{m}. \]

Step 2: Apply Big-Oh principle.
As \[ n \rightarrow \infty, \] the term \[ n^{m} \] grows much faster than \[ n^{m-1}, n^{m-2}, \ldots , n, 1. \] Hence the dominant term is \[ a_m n^m. \]

Step 3: Determine the complexity.
Ignoring constants and lower-order terms, \[ f(n)=O(n^m). \]

Step 4: Write the final answer.
Therefore, \[ \boxed{O(n^m)} \] Hence option (D) is correct.