Question

Give a big-O estimate for the size of f in Exercise \(1{20}\) if f is an increasing function.

Short answer

We have then shown that is \(O\left( {{n^4}} \right)\).

Step-by-step solution

Given data

Result previous exercise:

\(f(n) = \frac{{625}}{{311}} \cdot {n^4} - \frac{{314}}{{311}} \cdot {3^{{{\log }_5}n}}\)

Definition

Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.

Simplify O notation

Result previous exercise:

\(f(n) = \frac{{625}}{{311}} \cdot {n^4} - \frac{{314}}{{311}} \cdot {3^{{{\log }_5}n}}\)

Big-O Notation:isif there exist constantsandsuch that

\(|f(x)| \le C|g(x)|\)

whenever\(\;x > k\).
\(\begin{array}{*{20}{c}}{f(n)}&{\: = \frac{{625}}{{311}} \cdot {n^4} - \frac{{314}}{{311}} \cdot {3^{{{\log }_5}n}}}&{}\\{}&{ \le \frac{{625}}{{311}} \cdot {n^4}\:\:{\rm{Since}}\:{3^{{{\log }_5}n}} > 0}&{}\end{array}\)
Thus, we have then shown thatis \(O\left( {{n^4}} \right)\).