Sum of Squares/Square of Sum Difference

I am doing Project Euler problem #6. This is the question it asks:


The sum of the squares of the first ten natural numbers is,


$$1^2 + 2^2 + \ldots + 10^2 = 385$$


The square of the sum of the first ten natural numbers is,


$$(1 + 2 + \ldots + 10)^2 = 55^2 = 3025$$


Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.


Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

My implementation in Python is as follows:

def sum_of_squares(n):
    return sum([i**2 for i in range(1, n+1)])

def square_of_sum(n):
    return sum(range(1, n+1)) ** 2

print square_of_sum(100) - sum_of_squares(100)

It works but I was wondering if my implementation is good and fast enough?

Implementation is good indeed, but I have some reservations calling it fast. Its complexity is O(n). As usual (including, but not limited to, Project Euler), an ultimate optimizer is math. Recall that


$$ 1 + 2 + \ldots + n = \frac{n(n+1)}{2}$$

and


$$ 1^2 + 2^2 + \ldots + n^2 = \frac{n(n+1)(2n+1)}{6}$$

so the result


$$ \frac{n^2(n+1)^2}{4} - \frac{n(n+1)(2n+1)}{6} = \frac{(n-1)n(n+1)(3n+2)}{12}$$

can be achieved in O(1) time.

StackExchange Code Review Q#58460, answer score: 20