Algocademy Logo

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


Given a non-negative integer n, compute and return the sum of
12 + 22 + 32 + ... + n2

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 misunderstand the range of numbers to be squared or to overlook the efficiency of the solution.

Approach

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

Naive Solution

The naive solution involves iterating through each number from 1 to n, squaring it, and adding it to a running total. This approach is straightforward but not the most efficient for very large values of n.

Optimized Solution

An optimized solution 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 iterative approach.

Algorithm

Naive Approach

  1. Initialize a variable sum to 0.
  2. Iterate through numbers from 1 to n.
  3. For each number i, compute i * i and add it 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

public class SumOfSquares {
    public static int sumOfSquares(int n) {
        int sum = 0; // Initialize sum to 0
        for (int i = 1; i <= n; i++) { // Iterate from 1 to n
            sum += i * i; // Add the square of i to sum
        }
        return sum; // Return the computed sum
    }

    public static void main(String[] args) {
        int n = 3;
        System.out.println(sumOfSquares(n)); // Output: 14
    }
}

Optimized Approach

public class SumOfSquares {
    public static int sumOfSquares(int n) {
        // Use the formula to compute the sum of squares
        return n * (n + 1) * (2 * n + 1) / 6;
    }

    public static void main(String[] args) {
        int n = 3;
        System.out.println(sumOfSquares(n)); // Output: 14
    }
}

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:

Testing

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

n = 0; Expected output: 0
n = 1; Expected output: 1
n = 3; Expected output: 14
n = 10; Expected output: 385
n = 100; Expected output: 338350

Thinking and Problem-Solving Tips

When approaching such problems, consider both iterative and mathematical solutions. Understanding mathematical formulas can often lead to more efficient solutions. 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. Understanding and applying mathematical formulas can significantly improve the efficiency of your solutions. Keep practicing and exploring further to enhance your problem-solving abilities.

Additional Resources