Question

Find the least integer\(n\)such that\(f(x)\)is\(O({x^n})\)for each of these functions.

a)\(\;f(x) = 2{x^3} + {x^2}\log x\)

b)\(f(x) = 3{x^3} + {(\log x)^4}\)

c)\(f(x) = ({x^4} + {x^2} + 1)/({x^3} + 1)\)

d) \(f(x) = ({x^4} + 5\log x)/({x^4} + 1)\)

Short answer

a)\(n = 3\)

b)\(n = 3\)

c)\(n = 1\)

d) \(n = 0\)

Step-by-step solution

Subpart (a): \(\;f(x) = 2{x^3} + {x^2}\log x\)Step 1:

We know that\(\log x\)grows more slowly than\(x\)

\( \Rightarrow {x^2}\log x\)grows more slowly than\({x^3}\)

Here, first term is dominating

Step 2:

Therefore, this function is\(O({x^3})\)but not\(O({x^n})\)for any\(n < 3\)

\( \Rightarrow 2{x^3} + {x^2}\log x \le 2{x^3} + {x^3} = 3{x^3}\)for all\(x\)

\( \Rightarrow C = 3\) and \(k = 0\)

Subpart (b): \(f(x) = 3{x^3} + {(\log x)^4}\)Step 1:

We know that every power of\(\log x\)grows more slowly than\(x\)

\( \Rightarrow {(\log x)^4}\)grows more slowly than\(3{x^3}\)

Here, first term is dominating

Step 2:

\({(\log x)^4} < {x^3}\)for all\(x > 1\)

So,\(3{x^3} + {(\log x)^4} \le 3{x^3} + {x^3} = 4{x^3}\)for all\(x\)

\( \Rightarrow C = 4\) and \(k = 1\)

Subpart (c): \(f(x) = ({x^4} + {x^2} + 1)/({x^3} + 1)\)Step 1:

Using long division method in\(f(x) = ({x^4} + {x^2} + 1)/({x^3} + 1)\)we get

Remainder\({x^2} - x + 1\)

We can write the fraction as

\(f(x) = \frac{{{x^4} + {x^2} + 1}}{{{x^3} + 1}}\)as\(x + \frac{{{x^2} - x + 1}}{{{x^3} + 1}}\)

This function is \(O(x)\), so \(n = 1\)

Step 2:

\(f(x) = x + \frac{1}{{x + 1}} \le 2x\)for all\(x > 1\)

\( \Rightarrow C = 2\) and \(k = 1\)

Subpart (d): \(f(x) = ({x^4} + 5\log x)/({x^4} + 1)\)Step 1:

Using long division method in\(f(x) = ({x^4} + 5\log x)/({x^4} + 1)\)we get

Remainder\(5x - 1\)

We can write the fraction as

\(f(x) = \frac{{{x^4} + 5\log x}}{{{x^4} + 1}}\)as\(1 + \frac{{5x - 1}}{{{x^4} + 1}}\)

This function is \(O(1)\), so \(n = 0\)

Step 2:

Since,\(5\log x < {x^4}\)for\(x > 1\)

We have

\(f(x) \le \frac{{2{x^4}}}{{{x^4}}} = 2\)

\( \Rightarrow C = 2\) and \(k = 1\)