Find the smallest integer constant $c$ such that $f(n) = \mathcal{O}(n^c)$.
There are two parts to this.
In the first part, $f(n) = \dfrac{n^2}{2}$.
From what I understand, if $f(n) = \mathcal{O}(n^c)$, then $$\dfrac{f(n)}{n^c} \leq x \implies \dfrac{n^{2}}{2n^{c}} = x$$ where x is some constant.
I don't know how to proceed from here though.
In the second part, $f(n)$ is $n (\log_{2} n)^3$.
I don't know how to operate with logs. Some guidance would be appreciated.
$O(g(n))$ is often written in terms of limits (or limsup), but this definition can work.
$f(n)=O(g(n))$ if there exists a $C$ so that $\frac{f(n)}{g(n)}\leq C$ for all $n$.
In your first problem, you're trying to find $c$ and potentially $C$ so that $$ \frac{\frac{1}{2}n^2}{n^c}\leq C $$ for all $n$. Therefore, you need $$ n^{2-c}\leq 2C=K $$ (we can define $2C$ as a new constant $K$ because both are just constants). Therefore, you need to know the smallest $c$ where $n^{2-c}$ is bounded. If $c<2$, then the exponent is positive and the quantity grows as $n$ does. if $c=2$, then the exponent is $0$ and $n^0=1$, which is bounded. Therefore, the answer is $c=2$.
In your second problem, $c=2$. In $$ \frac{n(\log_2 n)^3}{n^c}, $$ if $c\leq 1$, then the fraction is $n^{1-c}(\log_2 n)^3$, which grows because the exponent on $n$ is nonnegative and $\log_2 n$ is increasing. On the other hand, for any $c>1$, the quantity is bounded (take the limit as $n$ approaches $\infty$). Therefore, $c=2$ will work.
