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

