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?

  • $\begingroup$ what does $\log ^2 n$ mean? $\endgroup$ – Arjang Feb 12 at 14:57
  • 1
    $\begingroup$ 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$. $\endgroup$ – Ivan Neretin Feb 12 at 15:18
  • $\begingroup$ 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. $\endgroup$ – user118462 Feb 12 at 15:21
  • 1
    $\begingroup$ 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) $$ $\endgroup$ – Calvin Khor Feb 12 at 16:01
  • $\begingroup$ Thank you. Why not post as an answer? $\endgroup$ – user118462 Feb 12 at 18:44

Your Answer

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

Browse other questions tagged or ask your own question.