Big-Oh Notation and Solving for f(x)

Question

Taking Discrete Mathematics and completely lost when it comes to Big-Oh Notation. While I know it's used to profile code I can't figure out how to solve the following problem:

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

a) $f(x) = 2x^2 + x^3 log(x)$

b) $f(x) = 3x^5 + log^4(x)$

... etc.

Answer 1

$f(x)$ is a $O(x^n)$ iff $|f(x)|\leq M|x^n|$ for any sufficiently large $x$. Hence

a) $f(x)\in O(x^4)$, but $f(x)\notin O(x^3)$ ...

Answer 2

I assume $x\in\mathbb{N}$.

*For Big $O$, $f(x)\in O(g(x))\Longleftrightarrow\exists c\in\mathbb{R}:\exists N_0\in\mathbb{N}:\forall x\in\mathbb{N},x\ge N_0,~|f(x)|\le c\cdot|g(x)|,~c\in\mathbb{R}$.

*For $\Omega$, $f(x)\in \Omega(g(x))\Longleftrightarrow\exists c\in\mathbb{R}_+:\exists N_0\in\mathbb{N}:\forall x\in\mathbb{N},x\ge N_0,~|f(x)|\ge c\cdot|g(x)|,~c\in\mathbb{R}$.

*For $\Theta$, $f(x)\in\Theta(g(x))\Longleftrightarrow f(x)\in\Omega(g(x))~\wedge~f(x)\in O(g(x))$.

So (in simplicity and abuse of notation):

• $f(x)\in\Omega(x^n)\Longleftrightarrow |f(x)|\ge c_1\cdot|x^n|$
• $f(x)\in O(x^n)\Longleftrightarrow |f(x)|\le c_2\cdot|x^n|$.
• $f(x)\in\Theta(x^n)\Longleftrightarrow c_1\cdot|x^n|\le|f(x)|\le c_2\cdot|x^n|$

---

a) $f(x)=2x^2+x^3\log(x)$
Asympotically $x^3\log(x)\ge2x^2$, so let's find the first $x$ such that that's true.
$\begin{array}{rclc} x^3\log(x) & \ge & 2x^2 & \\ x^3\log(x)-2x^2 & \ge & 0 & \\ x^2(x\log(x)-2) & \ge & 0 & \\ x\log(x)-2 & \ge & 0 & x\ne0\\ x\log(x) & \ge & 2 & \\ 10^{x\log(x)} & \ge & 10^2 & \\ \left(10^{\log(x)}\right)^x & \ge & 100\\ x^x & \ge & 100 & \\ \end{array}$

Since $100=2^2\cdot5^2$ and $2^2>3$ and $5^2>3^2\Longrightarrow x>3\Longrightarrow x\ge4$.
Also $2^2=4$ and $\sqrt{5^2}=5~\wedge~\sqrt{4^3}=4\sqrt{4}=8\Longrightarrow 100=2^2\cdot5^2\le4^4\Longrightarrow x\le4$.

So if $x\le4~\wedge~x\ge4\Longrightarrow x=4$.

Let's $N_0=4\Longrightarrow \forall x\in\mathbb{N}, x\ge N_0: x^3\log(x)\ge2x^2\Longrightarrow f(x)\le2x^3\log(x)$.

Let's find the least $n$ such that $x^n\ge x^3\log(x)$.
$\begin{array}{rcl} x^n & \ge & x^3\log(x)\\ \displaystyle\frac{x^n}{x^3} & \ge & \log(x)\\ x^{n-3} & \ge & \log(x) \end{array}$
Asympotically $1\le\log(x)\le x\Longrightarrow n-3=1\Longrightarrow n=4~\wedge~c=1$.
So $f(x)\in O(x^4)$.

Since $2x^2\ge0\Longrightarrow f(x)\ge x^3\log(x)\Longrightarrow f(x)\in\Omega(x^3\log(x))$.

Then there are no $n\in\mathbb{N}, n<4$ such that $f(x)\in O(x^n)$, so $n=4$ is the least number such that $f(x)\in O(x^n)$.

---

b) $f(x)=3x^5+\log^4(x)$
Since $x\ge\log(x)\Longrightarrow x^4\ge\log^4(x)~\wedge~x^5\ge x^4\Longrightarrow x^5\ge\log^4(x)$.
So $f(x)\le2x^5\Longrightarrow$ assume $c=2~\wedge~N_0=1\Longrightarrow f(x)\in O(x^5)$.

Since $\log^4(x)\ge0\Longrightarrow f(x)\ge x^5\Longrightarrow f(x)\in\Omega(x^5)\Longrightarrow f(x)\in\Theta(x^5)$.

So $n=5$ is the least number such that $f(x)\in O(x^5)$.