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

  • $\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$ – 6005 Mar 2 at 21:04

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

| cite | improve this answer | |
  • $\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 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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