1
$\begingroup$

$$ 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 ?

$\endgroup$
1
  • $\begingroup$ Can you provide your definition of C and N0? Different definitions use different variable names, so I'm not sure what you mean by them. $\endgroup$ Mar 2, 2020 at 21:04

1 Answer 1

2
$\begingroup$

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$!

$\endgroup$
1
  • $\begingroup$ I understand the concept well, it's the values I got that makes me confuse because after simplifying, I got c, and N0 with the same value which are c = 40 and N0 = 1, just need to know if I am on the right way. $\endgroup$
    – Sara Owen
    Mar 2, 2020 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.