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

Question

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.

Answer 1

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.