Sum of Squares in C++ (Time Complexity: O(n))

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

Understanding the Problem

The core challenge of this problem is to compute the sum of squares of the first n natural numbers efficiently. This problem is significant in various mathematical and computational applications, such as statistical calculations and algorithm analysis. A common pitfall is to overlook the efficiency of the solution, especially for large values of n.

Approach

To solve this problem, we can start with a naive approach and then discuss an optimized solution.

Naive Approach

The naive approach involves iterating through each number from 1 to n and summing their squares. This approach is straightforward but not the most efficient for very large values of n.

Optimized Approach

An optimized approach leverages the mathematical formula for the sum of squares of the first n natural numbers:

Sum = n(n + 1)(2n + 1) / 6

This formula allows us to compute the sum in constant time, O(1), which is significantly faster than the naive approach.

Algorithm

Naive Approach

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

Optimized Approach

1. Use the formula Sum = n(n + 1)(2n + 1) / 6 to compute the sum directly.
2. Return the computed value.

Code Implementation

Naive Approach

#include <iostream>

int sumOfSquaresNaive(int n) {
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        sum += i * i; // Add the square of i to sum
    }
    return sum;
}

int main() {
    int n = 3;
    std::cout << "Sum of squares (Naive): " << sumOfSquaresNaive(n) << std::endl;
    return 0;
}

Optimized Approach

#include <iostream>

int sumOfSquaresOptimized(int n) {
    return (n * (n + 1) * (2 * n + 1)) / 6; // Use the formula to compute the sum
}

int main() {
    int n = 3;
    std::cout << "Sum of squares (Optimized): " << sumOfSquaresOptimized(n) << std::endl;
    return 0;
}

Complexity Analysis

Naive Approach: The time complexity is O(n) because we iterate through each number from 1 to n. The space complexity is O(1) as we use a constant amount of extra space.

Optimized Approach: The time complexity is O(1) because we compute the sum using a constant-time formula. The space complexity is also O(1).

Edge Cases

Consider the following edge cases:

• n = 0: The sum should be 0.
• n = 1: The sum should be 1 (1²).
• Large values of n: Ensure the solution handles large values efficiently.

Testing

To test the solution comprehensively, consider the following test cases:

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

Thinking and Problem-Solving Tips

When approaching such problems, consider both the brute-force and optimized solutions. Understanding the underlying mathematical principles can often lead to more efficient algorithms. Practice by solving similar problems and studying different algorithms to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to compute the sum of squares of the first n natural numbers using both naive and optimized approaches. We analyzed the complexity of each approach and provided well-commented C++ code implementations. Understanding and solving such problems is crucial for developing efficient algorithms and improving problem-solving skills.

Additional Resources

• Square Number - Wikipedia
• Sum of Squares - GeeksforGeeks
• LeetCode - Coding Challenges