The Problem with Naive Implementations

Implement a function that calculates the sum of the first N natural numbers.

def sum(n: int) -> int:
    result = 0
    for i in range(n+1):
        result += i
    return result
sum_3 = sum(3)
print(sum_3)
    for i in range(n+1):
    result += i
import time
ranges = (10, 1000, 10000, 100000)
for n in ranges:
    sum(n)
ranges = (10, 1000, 10000, 100000)
for n in ranges:
    start = time.process_time_ns()
    sum(n)
    end = time.process_time_ns()
    exec_time = end — start
    print(f”sum({n}) exec time: {exec_time}ns”)
sum(10) exec time: 4000ns
sum(1000) exec time: 73000ns
sum(10000) exec time: 681000ns
sum(100000) exec time: 6990000ns

Applying a 2000-year-old Formula

sum(N) = n * (n+1) / 2
def sum_optimized(n: int) -> int:
    return n * (n + 1) / 2
sum_optimized(10) exec time: 3000ns
sum_optimized(1000) exec time: 2000ns
sum_optimized(10000) exec time: 2000ns
sum_optimized(100000) exec time: 2000ns
sum(10) exec time: 4000ns
sum(1000) exec time: 73000ns
sum(10000) exec time: 681000ns
sum(100000) exec time: 6990000ns

Leave A Comment