0
$\begingroup$

I have been studying asymptotic notation and I understand that in big O notation $f(n) <=c1*g(n)$ and in omega notation we have $f(n)>= c2*g(n)$ where $c1$ and $c2$ are some constant.

Now I was wondering if the function $g(n)$ here are the same and the big O and omega of $f(n)$ is determined by constants $c1$ and $c2$. Or if the $g(n)$ is different for O and omega.

If $g(n)$ is indeed same can anyone explain with example how is it possible as I can think of the examples in which $g(n)$ is different in both cases.

$\endgroup$

closed as unclear what you're asking by David Richerby, Evil, Juho, Gilles Sep 24 '16 at 21:22

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ I don't understand what you're asking. You seem to be confusing big-O notation and its definition. "In big O notation f(n) <=O( c1*g(n))" doesn't make any sense: I think you mean that "$f(n)=O(g(n))$ means that $f(n)\leq c_1\,g(n)$" (for large enough $n$). But I don't know what you mean by asking if the function $g(n)$ is the same. Big-O is a lot like "less than" for functions. So your question is a bit like saying, "I know what $x<a$ means and what $x>a$ means. But is it the same $a$?" $\endgroup$ – David Richerby Sep 15 '16 at 19:23
  • $\begingroup$ In particular, you can say that $x\leq 10$ and $xleq4$ but that doesn't mean that $4=10$. But you can also say $x\geq6$ and $x\leq6$. (I should really have used $\leq$ in my first comment.) $\endgroup$ – David Richerby Sep 15 '16 at 19:35
  • $\begingroup$ If you have $f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$, then the $g$'s are the same function (since you wrote it that way). On the other hand, if (unknown to you) you had $f(n)=n^2$, then it would be correct to say $f(n)=O(n^3)$ and $f(n)=\Omega(n)$, with different functions on the right. $\endgroup$ – Rick Decker Sep 15 '16 at 19:56
  • $\begingroup$ Yes, here if g(n) is the same function does upper and lower bound of f(n) then depend on c1 and c2. $\endgroup$ – Y0gesh Gupta Sep 15 '16 at 20:00
  • 1
    $\begingroup$ Not in general. To say, for instance, $f(n)=O(g(n))$ means that there is some $c>0$ and $N>0$ such that $f(n)\le c\,g(n)$ for all $n\ge N$. There are lots of choices for $c$: if you knew $f(n)\le c_1\,g(n)$ then certainly $f(n)\le c_2\,g(n)$ for any $c_2\ge c_1$. $\endgroup$ – Rick Decker Sep 15 '16 at 20:05
1
$\begingroup$

If you write down $f \in O(g)$ and $f \in \Omega(g)$ then you clearly intend both instances of "$g$" to refer to the same function. Otherwise, it would be pretty confusing.

Note how this is equivalent to $f \in \Theta(g)$.

If, however, you write down $f \in O(n^2)$ and $f \in \Omega(n)$ and want to unfold both the definition of $O$ and $\Omega$, you'll have to instantiate two different "$g$"s. That is, you'd write

$\qquad c_1 g_1(n) \leq f(n) \leq c_2 g_2(n)$

for all $n \geq n_0$ for some $c_1, c_2 > 0$ and $n_0 \geq 0$. Here, we know that $g_1 = n \mapsto n$ and $g_2 = n \mapsto n^2$.

$\endgroup$

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