O(1) solution for: 1+(1+2)+(1+2+3)+...+(1+2+3+...+n)

We can solve this in \(O(n)\) time if we apply the closed formula for sum of \(N\) numbers. We need to traverse up till \(N\) and for each iteration calculate the sum of \(N\) numbers. But do you know what's even better? You can do it in \(O(1)\) time. You just need to play with the same closed sum formula.

Let the \(N^{th} term\) of the series be \(S_{N}\),
\[S_{N} = \sum_{i=1}^{N} i = \dfrac{N(N+1)}{2} = \dfrac{N^2+N}{2}\\
\sum_{i=1}^{N} S_{N} = \sum_{i=1}^{N} \dfrac{N^2+N}{2}\\
= \dfrac{1}{2} \sum_{i=1}^{N} N^2 + \sum_{i=1}^{N} N\\
= \dfrac{1}{2} \dfrac{N(N+1)(2N+1)}{6} + \dfrac{1}{2} \dfrac{N(N+1)}{2}\\
= \dfrac{1}{2}N(N+1) [\dfrac{2N+1}{6} + \dfrac{1}{2}]\\
= \dfrac{N(N+1)(2N+4)}{12}\]
\[\therefore S_{N} = \dfrac{N(N+1)(2N+4)}{12}\]

Here is the code in C++:






Comments