# Harmonic series (double)

I am wondering about the $$\Theta$$ class (i.e. asymptotic complexity) of the following:

$$\sum^n_{i=1} \sum_{j=1}^n \frac{1}{ij}$$

Since this is basically the harmonic series, applied twice, it seems to me that the answer is $$\Theta(\log ^2 n)$$. Is this correct?

• what does $\log ^2 n$ mean? – Arjang Feb 12 at 14:57
• No, what does "complexity" mean? If you just want asymptotics, then yes, your sum is obviously the same as $\left(\sum\limits_{i=1}^n{1\over i}\right)^2$. – Ivan Neretin Feb 12 at 15:18
• I am a computer scientist analyzing the asymptotic complexity of an algorithm. I want only the \Theta class, yes, asymptotics. log^2 n means log n \times log n. – user118462 Feb 12 at 15:21
• your summands split as a product, and more generally $$\sum_n \sum_m (a_n b_m ) = \left(\sum_n a_n\right) \left(\sum_m b_m \right)$$ – Calvin Khor Feb 12 at 16:01
• Thank you. Why not post as an answer? – user118462 Feb 12 at 18:44