Start learning free

LESSON 139 OF 410 · LOOPS & GLOBAL VARIABLES

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

Practice Read the full explanation

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

Example:

Input: n = 3

Output: 14

Explanation:
12 + 22 + 32 = 1 + 4 + 9 = 14
Hints:

Where should we store this sum as we compute it?

We can use a variable sum, initially equal to 0. We have to iterate through the numbers 1 to n. How can we do this?

Let's use a for loop and a variable i to iterate through the numbers 1 to n. What should we do inside this loop?

Inside the loop, all we should do is add i * i to sum.
When the loop terminates, the answer lies in sum.

STEP 1 OF 4
    Ctrl + Enter to check

    PYTHON · LOOPS & GLOBAL VARIABLES

    Sum Of Squares in Python, explained

    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:

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

    1. Initialize sum to 0.
    2. Use a for loop to iterate from 1 to n.
    3. In each iteration, compute the square of the current number and add it to sum.
    4. 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:

    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free