Chapter 18, Problem 55E

Program Plan Intro

Big-O complexity measure for the polynomial:

The polynomial is a mathematical expression involving algebraic terms with one or more variables increased by co-efficient.

• It is also called as the order of notation that represents the approximate computing time of the function as a notation.
  • It is the term in a function that increases with the size of the problem. The computing time is referred as the complexity.
  • The highest power in the polynomial represents the Big-O complexity of algorithm.
• The size of problem and its complexity is represented on a power such as O (1), O (log₂N), O (N), O (N log₂N), O (N×N), .. O (2^N), O (N!).
• For example,
  • Consider the polynomial expression, ${\text{f(N)=N}}^{\text{3}}{\text{+ 50N}}^{\text{2}}\text{+ 10N + 25}$
  • In the above expression f(N) is of order N³, O(N³) in Big-O notation.
    • This expression states that for large values ‘N’ dominates the whole function.
    • But it does not mean that the remaining terms ${\text{50N}}^{\text{2}}\text{+ 10N + 25}$ is not important, it just becomes irrelevant when “N” becomes larger.

Explanation of Solution

b.

Given that,

The Big-O complexity measure for the polynomial ${\text{x}}^{\text{5}}\text{+ x}$ :

• Since, the Big-O complexity is the highest power in the polynomial, the highest power in ${\text{x}}^{\text{5}}\text{+ x}$ is. ${\text{x}}^{\text{5}}$
• In Big-O notation it is represented as ${\text{O(N}}^{\text{5}}\text{)}$

Explanation of Solution

c.

Given that,

The Big-O complexity measure for the polynomial ${\text{x}}^{\text{2}}\text{+ 124578}$ :

• Since, the Big-O complexity is the highest power in the polynomial, the highest power in ${\text{x}}^{\text{2}}\text{+ 124578}$ is ${\text{x}}^{\text{2}}$.
• In Big-O notation it is represented as ${\text{O(N}}^{\text{2}}\text{)}$

Explanation of Solution

d.

Given that,

The Big-O complexity measure for the polynomial $\text{x + 1}$ :

• Since, the Big-O complexity is the highest power in the polynomial, the highest power in $\text{x + 1}$ is x.
• In Big-O notation it is represented as $\text{O(N)}$