Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If we know

$$ E(Z_i) = H_i + H_{n - i + 1} - 2 $$

and $i \sim \sqrt n$.

Can we write:

\begin{align*} E(Z_i) & = H_i + H_{n-i+1} - 2 \\ & \sim \log i + \log (n-i+1) \\ & \sim \log \sqrt n + \log n \\ & \sim \frac 3 2 \log n \end{align*}

$H_n$ is Harmonic number.

(The original question is "How does $E(Z_i)$ vary when $i \sim \sqrt n$")

share|improve this question
What does $\sim$ mean for you? A standard convention is that $f(n) \sim g(n)$ iff $f(n)/g(n) = 1 + o(1)$. Under that convention, this is correct. –  Srivatsan Sep 17 '11 at 16:47
My book doesn't specify the definition of $\sim$, so I guess it's defined in the conventional way. But can we derive the result from the definition of $\sim$? –  ablmf Sep 17 '11 at 16:55
The trouble is: "the conventional way" differs from one branch of mathematics to another. So (unless you know what it is in THIS branch) you should ask. –  GEdgar Sep 17 '11 at 19:26
I agree with @GEdgar in that this is used in multiple senses (and one should be careful while consulting a paper or book). That's why even my answer starts with "One fairly standard...". I guess that this question/doubt must have figured in some combinatorics/discrete math/algorithms context, and my answer implicitly assumes that. I will make this explicit in the beginning of my answer. –  Srivatsan Sep 17 '11 at 19:34
So note: you are using $f(n) \sim g(n)$ implies $\log f(n) \sim \log g(n)$, which is OK when they go to infinity. But some similar things don't work. $f(n) \sim g(n)$ need not imply $e^{f(n)} \sim e^{g(n)}$, for example. –  GEdgar Sep 17 '11 at 19:41
show 4 more comments

1 Answer

up vote 1 down vote accepted

Added: As GEdgar points out in a comment, what the symbol $\sim$ means depends a lot on the branch of mathematics. From the overall question, I am guessing that the branch in this case is either combinatorics or discrete mathematics or algorithms. I think my definition below agrees with popular usage of $\sim$ in these areas. See this page for further details.

One fairly standard convention is that for nonnegative eventually positive1 functions $f(n)$ and $g(n)$ $$ f(n) \sim g(n) \stackrel{\text{def}}{\iff} \lim_{n \to \infty} \frac{f(n)}{g(n)} = 1 \iff \frac{f(n)}{g(n)} = 1 + o(1) \iff f(n) = g(n) + o(g(n)), $$ where "def" means that we are defining $\sim$ this way.

1Added: I made the functions eventually positive. If $g(n)$ is zero infinitely often, then the limit does not exist. This is not the most general way to define asymptotic notation, but I find the restriction convenient.

I first state a basic fact about this asymptotic notation: if $f_1(n) \sim g_1(n)$ and $f_2(n) \sim g_2(n)$, then
$$ f_1(n) + f_2(n) = g_1(n) + o(g_1(n))+ g_2(n) + o(g_2(n)) = g_1(n)+g_2(n) + o(g_1(n) + g_2(n)), $$ so that $f_1(n) + f_2(n) \sim g_1(n) + g_2(n)$.

Coming to your question, we need the additional two facts:

  1. If $n$ is large, then $H_n \sim \log n$, which comes the estimate $$ H_n = \log n + \gamma + O(1/n) = \log n + O(1) = \log n + o(\log n). $$
  2. If $i \sim \sqrt{n}$, then $$ \log i = \log \sqrt{n} + \log \left(\frac{i}{\sqrt{n}} \right) = \log \sqrt{n} + \log (1+o(1)) = \log \sqrt{n} + o(1); $$ $$ \log(n-i+1) = \log n + \log \left( 1 - \frac{i-1}{n} \right) = \log n + \log (1 - o(1)) = \log n + o(1). $$ Hence certainly $\log i = (1 + o(1)) \log \sqrt{n}$ and $\log (n-i+1) = (1+ o(1)) \log n$.

Applying the above facts, you can see that the above asymptotic analysis is sound.

share|improve this answer
In your definition you say "nonnegative" but I would require that $g$ is eventually positive. –  GEdgar Sep 17 '11 at 19:27
@GEdgar Yes, thanks for the catch. I will make the functions positive, at least eventually. –  Srivatsan Sep 17 '11 at 19:30
add comment

Your Answer


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

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