

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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|cite|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
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|cite|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

Your Answer


