I'd be glad for an explanation on the analysis of this exercise. Given these functions: $$f(n) = n^2 \\ g(n) = n^{2/3}$$

Show that $f(n) = O(g(n))$, or $f(n) = \Omega(g(n))$ and comment if $f(n) = \Theta(g(n))$

In my answer, it is $\Theta(g(n))$ with $n_0 = 1, C = 1$

PS: The exercise requires a mathematical demonstration of the answer.

  • $\begingroup$ It looks incorrect. can you please add more details as to how you got this answer? $\endgroup$
    – Apoorv
    Feb 20, 2020 at 19:24
  • $\begingroup$ For instance: $n^{1/2} \leq C * n^{2/3} => \frac{n^{1/2}}{n^{2/3}} \leq C$. If we replace the variables with $1$, the assumption is satisfied. $\endgroup$ Feb 20, 2020 at 19:31
  • $\begingroup$ Same goes to $\Omega$ $\endgroup$ Feb 20, 2020 at 19:31
  • 1
    $\begingroup$ Please recheck the definitions of $\Omega, \Theta, O$ especially about the condition of n’s that you have to choose. $\endgroup$
    – Apoorv
    Feb 20, 2020 at 19:33
  • $\begingroup$ $\Omega$ means that there is a function multiplied by a constant that is $\leq$ than $f(n)$ for an existing $n_0, C$. $O$ is the upper bound and $\Theta$ means that there is both boundaries. $\endgroup$ Feb 20, 2020 at 19:36


Your Answer

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