# Proving big-theta complexity with constants in $f(n)$

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.

• 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$. – plop Feb 11 at 19:24
• 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)$. – Steven Feb 11 at 19:42
• 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. – plop Feb 11 at 19:53
• Thank you for the help all. – John McIntyre Feb 11 at 21:00

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.