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.
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):
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)$.
$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)$ ...
