Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
$$ 5n^4\log{n} - \frac{100n^2}{\log_4(n^2)} + 40 $$
I am currently studying algorithm analysis and i need to express this function in terms of big O, theta and omega, so I should find C, and N0 for each case I solved big Oh with c=40 and n0 = 1 but I am stuck here any help ?
If you check the definitions, big-O means "bounded from above" (with a fudging constant $c$ multiplying it all, starting at a high enough $n$), you can disregard "constants multiplying" and "slower growing terms"; so you can say:
$\begin{equation*} 5 n^2 \log n - \dfrac{100 n^2}{\log_4 n^2} + 40 = O(n^2 \log n) \end{equation*}$
(could also say $O(n^3)$, or $O(n^4 \log^{10} n)$ for that matter, bound from above).
For a lower bound, the same works fine:
$\begin{equation*} 5 n^2 \log n - \dfrac{100 n^2}{\log_4 n^2} + 40 = \Omega(n^2 \log n) \end{equation*}$
For a lower bound, $\Omega(1)$ or $\Omega(n \log n)$ work fine too.
As you have the same upper/lower bound:
$\begin{equation*} 5 n^2 \log n - \dfrac{100 n^2}{\log_4 n^2} + 40 = \Theta(n^2 \log n) \end{equation*}$
Finding values of $c$ and $N_0$ I leave to you. They can be different for $O$ and $\Omega$!
