Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have just encountered the following question: Let $C_n$ be a sequence of real numbers with the following three properties: 1) $C_n$ is subadditive, such that $$C_{m+n} \leq C_m +C_n$$

2) $C_n=O(\sqrt{n})$

3) $$C_{q+1} \leq 2 \sqrt{q}$$ for every prime power $q=p^m$

But I have no idea what's the use of the first condition in order to prove that: $$\lim_n \sup \frac{C_n}{2\sqrt{n}} \leq 1$$

share|cite|improve this question
Perhaps you mean $\le1$? Because $C_n=0$ identically seems to be a counterexample. – anon Sep 11 '11 at 21:34
@anon: Would $C_n=0$ satisfy $C_n=O(n)$? Normally, a constant function is $O(1)$, not $O(n)$. – Arturo Magidin Sep 11 '11 at 21:37
@Arturo: $|0|\le1\cdot|n|$ for all $n\ge0$, so I believe it's $O(n)$. In analytic number theory there's lots of discussion of improving exponents in big-$O$ asymptotes, so just because $O(n)$ can be improved to $O(1)$ here doesn't mean $O(n)$ isn't true as well. There might be some convention that distinguishes an exponent of $0$ I'm not aware of, but that would seem to contradict the definition of $O$. What say you? – anon Sep 11 '11 at 22:08
@anon: I'm honestly asking, not correcting. I don't usually work with $O$ notation. Looking at the definition given in Apostol's "Intro to Analytic Number Theory", though, I see that if $f$ is $O(1)$, then it would also be $O(n)$. – Arturo Magidin Sep 11 '11 at 22:16
@Thijs: Maybe you have this question in mind? – t.b. Sep 11 '11 at 22:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.