# Struggling with asymptotic analysis

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.

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

## 1 Answer

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

• What about $f(n) = O(g(n))$? Feb 20 '20 at 19:52
• $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. Feb 20 '20 at 19:56
• 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. Feb 20 '20 at 19:58
• I am not quite sure I understand what you are asking for then. Feb 20 '20 at 20:00
• 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$ Feb 20 '20 at 20:02