Sum of Squares in Python (Time Complexity: O(n))

Given a non-negative integer n, compute and return the sum of
1² + 2² + 3² + ... + n²

Example:

Input: n = 3

Output: 14

Explanation:
1² + 2² + 3² = 1 + 4 + 9 = 14

Understanding the Problem

The core challenge of this problem is to compute the sum of squares of the first n natural numbers. This problem is significant in various mathematical and computational applications, such as in statistical formulas and algorithm analysis.

Potential pitfalls include misunderstanding the range of numbers to sum (from 1 to n) and ensuring the correct calculation of squares.

Approach

To solve this problem, we can use a simple iterative approach:

Initialize a variable sum to 0.
Iterate through numbers from 1 to n.
For each number i, add i * i to sum.
Return the value of sum.

This approach is straightforward and easy to understand. However, it is not the most optimized in terms of mathematical elegance.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Initialize sum to 0.
Use a for loop to iterate from 1 to n.
In each iteration, compute the square of the current number and add it to sum.
After the loop ends, return the value of sum.

Code Implementation

def sum_of_squares(n):
    # Initialize the sum to 0
    total_sum = 0
    
    # Iterate from 1 to n
    for i in range(1, n + 1):
        # Add the square of i to the total sum
        total_sum += i * i
    
    # Return the computed sum
    return total_sum

# Example usage
n = 3
print(sum_of_squares(n))  # Output: 14

Complexity Analysis

The time complexity of this approach is O(n) because we iterate through the numbers from 1 to n once. The space complexity is O(1) as we only use a constant amount of extra space for the sum variable.

Edge Cases

Potential edge cases include:

n = 0: The sum should be 0.
Large values of n: Ensure the algorithm handles large inputs efficiently.

Examples:

sum_of_squares(0)  # Output: 0
sum_of_squares(1)  # Output: 1
sum_of_squares(1000)  # Output: 333833500

Testing

To test the solution comprehensively, consider a variety of test cases:

Simple cases: n = 1, 2, 3
Edge cases: n = 0
Large cases: n = 1000, 10000

Example test cases:

assert sum_of_squares(0) == 0
assert sum_of_squares(1) == 1
assert sum_of_squares(2) == 5
assert sum_of_squares(3) == 14
assert sum_of_squares(10) == 385
assert sum_of_squares(1000) == 333833500

Thinking and Problem-Solving Tips

When approaching such problems:

Break down the problem into smaller, manageable parts.
Consider both naive and optimized solutions.
Think about edge cases and how to handle them.
Practice similar problems to improve problem-solving skills.

Conclusion

Understanding and solving the sum of squares problem helps in grasping basic iteration and summation concepts. It is a fundamental problem that appears in various mathematical and computational contexts. Practice and exploration of similar problems can further enhance problem-solving abilities.

Additional Resources

For further reading and practice: