0
$\begingroup$

Suppose the following is true for some f(n) and g(n): $f(n) = \Theta(g(n))$

Does that mean $f(n/k) = \Theta(g(n))$ for any value of $k>0$?

I know that for the above to be true, there must exist positive constants $c_1$, $c_2$, $n_0$ such that for all $n \geq n_0, $ $c_1(g(n)) \leq f(n) \leq c_2(g(n))$. Thus if $f(n) = \Theta(g(n))$, then can I assume:

$\frac{1}{k}c_1(g(n)) \leq f(n/k) \leq \frac{1}{k}c_2(g(n))$ to satisfy big Theta?

My apologies if this is totally obvious or if I'm completely on the wrong track, my math background isn't the strongest. Are there any relevant properties that might describe this relationship?

$\endgroup$
1
  • $\begingroup$ belongs to big Theta like in belongs to daddy? I think you should mention $g$ in the title. satisfy big Theta? Can you give a reference for such use of the Bachmann–Landau notation? $\endgroup$
    – greybeard
    Sep 21 '20 at 7:27
1
$\begingroup$

Take $f(n) = n^4$. For this function, if you double the argument, the result is multiplied by 16, that is by a constant factor. Now take $g(n) = 2^n$. For this function, if you double the argument, the result is squared, and since $2^n$ can grow arbitrarily large, there is no limit to the growth factor achieved by squaring g(n).

That’s the difference. If the growth from doubling the argument has an upper limit then $\Theta$ stays the some, otherwise it doesn’t.

$\endgroup$
0
1
$\begingroup$

Suppose $f(n) = 2^n$. Then $f(n / 2) = 2^{n / 2} = \sqrt{2^n}$ and setting e.g. $g(n) = 2^n$ as well shows $f(n) \in \Theta(g(n))$ but $f(n / 2) \notin \Theta(g(n))$, so this does not hold in general.

$\endgroup$
2
  • $\begingroup$ The first part is correct, but the last part seems wrong... $(n/2)^2 = n^2/4 = \Theta(n^2)$. $\endgroup$ Sep 21 '20 at 2:52
  • $\begingroup$ Yup, you are right. I deleted that part. Turns out my thinking abilities deteriorate after midnight :) $\endgroup$ Sep 21 '20 at 16:17
0
$\begingroup$

For given $f(n)$, well defined, for $\forall n\in \mathbb{N}$, the function $f(n/x)$ can be even undefined: for example $f(n)=\frac{1}{n-\frac{1}{2}}$ and $x=2$.

More sophisticated example is $$ f(n)=\begin{cases} 2^k, & n=2k+1 \\ k, & n=2k \end{cases} $$ Obviously $f(2n) \in \Theta(n)$, but $f(n)\notin \Theta(n)$.

Case, where your sentence is true is, for example, homogeneous function with homogeneous degree $k=1$ i.e. when $g(Cx)=Cg(x)$ and we consider homogeneous functions subset from $\Theta(g)$.

$\endgroup$
4
  • $\begingroup$ This doesn't seem super relevant, because (1) we usually assume total monotone-increasing natural number functions when working with big-O notation for program complexity, with rounding of real functions being fudged into meaninglessness by the hidden constants; and (2) big-O is all about limits, so behavior at a finite set of inputs doesn't really matter. $\endgroup$ Sep 21 '20 at 2:56
  • $\begingroup$ @Aaron Rotenberg. This example gives you possibility to imagine function which is undefined, for example, on middle of each interval $(n,n+1)$ and defined on ends of it. Here vanishes your argument about finite set, when first one is very restrictive. $\endgroup$
    – zkutch
    Sep 21 '20 at 3:09
  • $\begingroup$ Certainly true, in a very literal sense. But my point is that I don't think that would ever be relevant in e.g. a conference-level CS paper, because it is usually assumed that big-O notation in a complexity context can be treated as applying to functions of type $\mathbb{N} \rightarrow \mathbb{N}$ and an argument such as $n/2$ is rounded in some fashion that has no bearing on correctness. It's like arguing that a formula is wrong because the nested fraction notation $a/b/c$ is ambiguous: if it wasn't clear from context, the author shouldn't have done that. $\endgroup$ Sep 21 '20 at 3:16
  • $\begingroup$ @Aaron Rotenberg. Ambiguity of sentence is author's responsibility, not reader's. When you wrote "rounded" you should specify which one of all existing rounding methods you mean or, without it, you have pretension about proof for all known rounding methods. Author should provide well written text and clearly eliminate ambiguities and I am not speaking about some type of article, but, even, simple homework. $\endgroup$
    – zkutch
    Sep 21 '20 at 10:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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