0
$\begingroup$

I'm trying to compute time complexity for computing sum of first $\mathbf{n}$ squares. Actually, this is a problem from the textbook (A course in number theory and cryptography).

The question is to compute time complexity for LHS and RHS of the formula: $\sum_{j=1}^n j^2 = \frac{n(n+1)(2n+1)}{6}$

The answers from the textbook says $O(n{log}^2{n})$, but I found tighter bound for the algorithm as $O(log^2{n})$.

The reason is: We think of an algorithm as summing $1 \times 1$, $2 \times 2$, ..., $n\times n$ (Total of $n$ steps)

On $j$-th step, the length is $O(log^2{j})$. Summing $n$ terms, $O(log^2{1})+O(log^2{2})+...+O(log^2{n})\leq C*O(log^2{n})$, where $C$ is a constant.

Therefore, I got $Time(LHS)=O(log^2{n})$.

Is this correct? if I got wrong, could you tell me why?

thanks a lot :)

$\endgroup$
  • $\begingroup$ There is no constant $C$ that can satisfy your inequality. $\endgroup$ – Yves Daoust Mar 25 at 13:10
1
$\begingroup$

The problem is that your $C$ isn't a constant, it depends on $n$. The larger $n$ is, the more terms you have, and the sequence $\ln^2 n$ doesn't grow fast enough for the final few terms to dominate. This means that your $C$ must grow with $n$.

$\endgroup$
  • $\begingroup$ Ooops that was a silly question. So each $ln^2{j}$'s are bounded by $ln^2{n}$ and there are n such terms, so the time complexity becomes $O(n*ln^2{n})$. $\endgroup$ – Cryptomath Mar 25 at 13:13
  • $\begingroup$ @JHLEE Yes. At least that proves that it cannot be $O(\ln^2 n)$. Proving that $O(n\ln^2 n)$ is in some sense the best one can do (that it's not, say $O(\sqrt n\ln^2 n)$) is a slightly different matter. $\endgroup$ – Arthur Mar 25 at 13:17
  • $\begingroup$ Got it. Thx a lot! $\endgroup$ – Cryptomath Mar 25 at 13:18

Your Answer

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

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