1
$\begingroup$

I am working through a problem in which I have to prove that a particular $f(n) = \Theta(g(n))$. I know that for this to be true there need to exist positive constants $c_1$, $c_2$, and $n_0$ such that for all $n \geq n_0$, $c_1g(n)\leq f(n) \leq c_2g(n)$. Simply put, the goal is to pick values for the constants such that the above inequality holds. As a side note, $n$ must be a positive integer, and $c_1$ and $c_2$ can be any positive real number, correct? I haven't been able to find clarity over that.

Now, suppose the $f(n)$ has some undefined constants $a$ and $b$, such as $f(n) = n^a + n^b$. Note that this is a throwaway example. My question is this: do we need to define $c_1$ and $c_2$ in terms of the constants $a$ and $b$, or do we need to pick an actual numerical value for $c_1$ and $c_2$, and by extension, values for $a$ and $b$? The former is much more difficult to do.

I apologize in advance for the poor formatting (I simply placed any math in italics, which I know is not correct). This is my first ever post on CS stack exchange. Also, I would like to state that there was a serious attempt at researching into the above, but I couldn't find examples of how to prove $f(n) = \Theta(g(n))$ when $f(n)$ has other constants. If anyone has resources related to this, I would be very grateful.

I would appreciate any and all help. Looking forward to potential responses.

$\endgroup$
4
  • 1
    $\begingroup$ Yes, the constants $c_1,c_2$ depend on the function $f$. In your throwaway example, since $f$ depends on $a$ and $b$, incidentally $c_1,c_2$ depend, in principle, on $a$ and $b$. $\endgroup$
    – plop
    Feb 11, 2021 at 19:24
  • $\begingroup$ And, in addition to what plop said: yes, $c_1$ and $c_2$ are positive real numbers. If you only care about proving that $f(n)=\Theta(g(n))$ (and not about the specific values of $c_1$, $c_2$, and $n_0$), then there are usually sufficient conditions that are easier to show. For example you could just show that $\lim_{n\to +\infty} \frac{f(n)}{g(n)}$ exists, is finite, and is positive. Then, if $\ell = \lim_{n\to +\infty}$, you know that for any pair of constants $c_1, c_2$ with $0 < c_1<\ell < c_2$, there is some large enough $n_0$ that will satisfy the definition of $\Theta(\cdot)$. $\endgroup$
    – Steven
    Feb 11, 2021 at 19:42
  • $\begingroup$ The values of $c_1$ is any number in the interval $\left(0,\liminf\frac{f(n)}{g(n)}\right)$ and the values of $c_2$ is any number in the interval $\left(\limsup\frac{f(n)}{g(n)},+\infty\right)$.Sometimes the values of the liminf and linsup themselves can be used, but not always. $\endgroup$
    – plop
    Feb 11, 2021 at 19:53
  • $\begingroup$ Thank you for the help all. $\endgroup$ Feb 11, 2021 at 21:00

1 Answer 1

0
$\begingroup$

You can find the definitions of big O notations on Wikipedia. They agree with your definition of big $\Theta$.

As for your actual question, the answer is actually quite subtle. Sometimes it is possible to find constants $c_1,c_2,n_0$ which work for all values of the parameters. For example, in your case, all $n \geq 1$ satisfy $$ 1 \cdot n^{\max(a,b)} \leq n^a + n^b \leq 2 \cdot n^{\max(a,b)}, $$ and so you can say that $n^a + n^b = \Theta(n^{\max(a,b)})$.

(As a side note, you can also say that $n^a + n^b = \Theta(n^a + n^b)$, or that $n^a + n^b = \Theta(n^a + 2n^b)$; but usually we aim at the simplest possible expression, or an expression of a particular form, say $n^\alpha \log^\beta n$.)

In other cases we are not so lucky. For example, $\log^k n = O(n)$ for all $k$, but the relevant constants depend on $k$. Sometimes this makes no difference, but in other cases it is important to know that the constants depend on $k$. When it does matter, we sometimes use the notation $O_k(n)$ to stress that the hidden constants depend on $k$. This is not completely standard, but pretty common. When the hidden constants are independent of some parameter, we can explicitly say so – $n^a + n^b = \Theta(n^{\max(a,b)})$, where the hidden constants are independent of $a,b$.

In your case, since you are only interested in an isolated estimate, you don't care about the dependence of the hidden constants on the parameters. So for you, $\log^k n = O(n)$ holds, even though the hidden constants depend on $k$, since for any particular $k$ this statement holds. This is the usage in the master theorem, for example – the constants there depend on the parameters, but usually it makes no difference, because the parameters are fixed in any given application, in the vast majority of circumstances.

$\endgroup$

Your Answer

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

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