0
$\begingroup$

I'd be glad for an explanation on the analysis of this exercise. Given these functions: $$f(n) = n^{1/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))$

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

$\endgroup$
2
  • $\begingroup$ In my solution, it is $\Theta(g(n))$ taking $n_0 = 1$ and $C = 1$ $\endgroup$
    – joann2555
    Feb 20 '20 at 18:24
  • $\begingroup$ Did you finish this problem? $\endgroup$
    – Axion004
    Aug 14 '20 at 0:02
0
$\begingroup$

Given $f(n) = n^{1/2}$ and $g(n) = n^{2/3}$, we can see that $f(n) = \O(g(n))$, because the function $g(n)$ grows faster than the function $f(n)$. We can demonstrate this writing the values for a series of inputs $0, 1, ...$ to $f(n)$ and $g(n)$:

$f(0) = 0$

$g(0) = 0$

$f(1) = 1$

$g(1) = 1$

$f(2) = 1.4$

$g(2) = 1.6$

$f(3) = 1.7$

$g(3) = 2$

$\endgroup$
9
  • $\begingroup$ What about $f(n) = O(g(n))$? $\endgroup$
    – joann2555
    Feb 20 '20 at 19:52
  • $\begingroup$ $f(n) = O(g(n))$ would not be true since the $f(n)$ grows faster. However, you can write $g(n) = O(f(n))$. Maybe it will help to visualize Big-O as '$\leq$' and Omega as the opposite. $\endgroup$ Feb 20 '20 at 19:56
  • $\begingroup$ I understand the order of growth. In fact, i must have said that the exercise requires the mathematical demonstration of the answer. That's where i'm struggling with. $\endgroup$
    – joann2555
    Feb 20 '20 at 19:58
  • $\begingroup$ I am not quite sure I understand what you are asking for then. $\endgroup$ Feb 20 '20 at 20:00
  • $\begingroup$ For instance, this is how i reached my answer: $n^{1/2} \leq C * n^{2/3} => \frac{n^{1/2}}{n^{2/3}} \leq C$ $\endgroup$
    – joann2555
    Feb 20 '20 at 20:02

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.