Time Complexity with a Simple Yet Powerful Example

Have you ever wondered why some code runs lightning-fast while others take much more time in comparison ? The secret lies in time complexity—a concept that can set apart an average coder from an efficient problem-solver. So , let’s uncover this through a real-world programming scenario: finding the sum of the first N natural numbers.

The Problem :- Sum of N Natural Numbers

Imagine you're building a game where a player earns points after crossing levels. The total score at any level N is simply:

Use a loop. But is it the best way?

📝(Using a While Loop)

# Function to calculate sum of first N natural numbers
def sum_of_natural(n):
    sum = 0                  # O(1)
    finalLevel = n           # O(1)
    currentLevel = 1         # O(1)
    
    while currentLevel <= finalLevel:
        sum += currentLevel  # O(n)
        currentLevel += 1    # O(n)
    
    return sum               # O(1)        

Time Complexity Breakdown:

• Initializations: O(1)
• While loop runs N times, performing O(1) + O(1) = O(n) operations.
• Total Complexity: O(1 + 1 + 1 + n + n + 1) = O(2n) = O(n) (Linear Time)

What does this mean? As 'n' grows, execution time increases proportionally.

Benchmarking Performance with %timeit

Want proof? Test execution speed using Jupyter Notebook:

%timeit sum_of_natural(7)
%timeit sum_of_natural(1000000)        

The Smart Approach (Mathematical Formula)

Instead of iterating, why not use a formula?

def sum_of_natural_optimized(n):
    return (n * (n + 1)) // 2  # O(1)        

Time Complexity: O(1) (Constant Time)

Why is this better? Unlike the loop-based approach (O(n)), this runs in the same time regardless of N.

Some final points :

✅ Understanding time complexity helps in writing efficient code.

✅ Loops run in O(n) time, while mathematical formulas reduce it to O(1).

✅ Optimized algorithms scale better in real-world applications.

✅ Benchmarking execution time gives real-world performance insights.