Skip to main content

What is Time Complexity?

Time complexityis a way to describe how therunning time of an algorithm growsas theinput size increases.

In simple terms:

How muchmore timedoes your program take when theinput growsfrom 10 items to 10,000?

📊 Big-O Notation – Common Time Complexities​

Time ComplexityDescriptionExample
O(1)Constant time – doesn't growAccessing an array element
O(log n)Logarithmic – grows slowlyBinary search
O(n)Linear – grows in proportionLoop through an array
O(n log n)QuasilinearMerge sort, quicksort
O(n²)Quadratic – slowNested loops
O(2ⁿ), O(n!)Exponential – very slowRecursive combinatorics

🛠️ Why Is Time Complexity Important in Software Engineering?​

1. Performance Prediction Before running code on massive data:

Will it scale, or crash?

2. Optimization It helps you move from:

  • O(n²) → O(n log n) for better performance
  • Or decide whether tooptimize or scale hardware

3. Coding Interviews Used byMeta/Facebook, Google, Amazon:

  • To assess algorithmic thinking
  • To ensure you're aware of scalability trade-offs

4. Engineering Decisions Complexity informs:

  • Flat files vs indexed DB?
  • Cache vs recompute?

🌍 Is Time Complexity Useful Outside of Software Engineering?​

Yes — anywhere algorithms are used:

🧬 Bioinformatics

  • DNA sequence matching
  • Protein folding

💰 Finance

  • High-frequency trading
  • Real-time fraud detection

🌐 Data Science & AI

  • Model training performance
  • Batch processing large datasets

🔐 Cryptography & Research

  • Encryption strength
  • P vs NP problems

🧪 How Is Time Complexity Measured?​

Youdon't time the code with a stopwatch— instead, youanalyze the number of operationsthe algorithm performs as the input grows.

Let's take a closer look.

Example: Looping and Time Complexity​

for i in range(n):         # Outer loop runs n times → O(n)
    for j in range(n):     # Inner loop runs n times for each i → O(n)
        print(i, j)        # Executes n * n times → O(n²)

This is called nested looping, and the total number of print(i, j) operations depends on both loops:

  • The outer loop runs n times.
  • For each iteration of the outer loop, the inner loop runs n times.
  • So the total number of operations is n * n = n²

We call this O(n²) or quadratic time.

  • If n = 10, the loop runs 100 times.
  • If n = 1,000, it runs 1,000,000 times.

As you can imagine how quickly this becomes slow and unscalable.

🤔 Is All Looping Bad?

Not at all! Looping is necessary — but we want to be smart about it.

The goal is to reduce unnecessary work, especially when we're processing large data sets.

This is where algorithmic patterns come into play — patterns that let us loop smarter, not harder.

Next: Looping Smartly with the Sliding Window Pattern

One of the simplest and most powerful tools in your algorithm toolkit is the sliding window.

It allows you to solve many subarray and substring problems in linear time (O(n)), where a naive solution might take O(n²).

Let's explore how this works — next up. Sliding Window: A Smarter Way to Loop