ReviseAlgo Logo

Foundations

Time Complexity

Learn how to measure and compare algorithm execution time as input size grows, without relying on clock speed.

Last Updated: July 31, 2026 • 15 min read

1. Introduction

What is Time Complexity?

Time Complexity is a way to describe how the execution time of a program changes as the input size grows larger. It counts the number of fundamental operations (like comparisons, additions, or assignments) an algorithm performs.

Why is it Important?

Measuring time in seconds is unreliable because a fast laptop runs code quicker than an older phone. Time complexity provides a universal, hardware-independent metric to compare which algorithm is truly more efficient.

Where is it Used?

  • High-Throughput Systems: Ensuring web servers can process 1,000,000 requests per minute without crashing.
  • Database Indexing: Ensuring lookups take milliseconds even when a database grows from 1,000 to 1,000,000,000 records.

    • 2. Mental Model

    Imagine you want to find a contact's phone number.

  • If the phonebook has 100 pages, Approach A takes up to 100 checks, while Approach B takes ~7 checks.
  • If the phonebook grows to 1,000,000 pages, Approach A takes up to 1,000,000 checks, while Approach B takes only 20 checks!

    • Time complexity focuses on how the workload scales when input increases tenfold or a millionfold.

    3. Concept: Counting Operations

    Instead of using a stopwatch, computer scientists measure efficiency by counting basic operations.

    Example 1: Constant Operations (Independent of N)

    Looking up an item by index in an array:

    This is Constant Time—the work stays the same no matter how big N gets.

    Example 2: Linear Operations (Grows with N)

    Checking every element in a list:

    This is Linear Time—if input size doubles, the work doubles.

    Example 3: Quadratic Operations (Grows with N²)

    Comparing every element with every other element (nested loops):

    This is Quadratic Time—small increases in input lead to massive explosions in total operations.

    4. Visuals

    Growth of Operations as Input (N) Increases

    Input Size (N)Constant O(1)Logarithmic O(log N)Linear O(N)Quadratic O(N²)
    101 operation~3 operations10 operations100 operations
    1001 operation~7 operations100 operations10,000 operations
    1,0001 operation~10 operations1,000 operations1,000,000 operations
    1,000,0001 operation~20 operations1,000,000 operations1,000,000,000,000 operations (CPU hangs!)

    5. Real-World Examples

  • Social Media Feed (Instagram/X): Fetching your user profile by ID is O(1). Scanning every post on the platform to count total likes without an index is O(N).
  • Autocomplete (Google Search): Traversing a Trie tree of words matching prefix "rec..." is O(K) where K is prefix length, allowing instant suggestions among billions of words.
  • E-Commerce Price Filter (Amazon): Sorting 100,000 products by price using QuickSort takes O(N log N) time (~1.6 million operations), making page rendering instant.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    After you propose a solution, interviewers will ask: "What is the time complexity of your approach?"

    Common Mistakes

    Warning: 1. Confusing Clock Seconds with Time Complexity: Saying "This algorithm takes 2 milliseconds" instead of analyzing operation growth O(N).
    > 2. Ignoring Hidden Loops: Calling built-in functions like indexOf(), contains(), or string concatenation inside a loop without realizing they add an inner O(N) factor.
    > 3. Counting Non-Dominant Operations: Worrying about 2N + 5 operations instead of focusing on the dominant growth rate O(N).

    Important Interviewer Tips

  • Always identify the main input parameters (e.g. N = number of elements, M = string length).
  • State time complexity proactively before the interviewer asks!

    • 7. Summary

  • Time complexity measures operation growth rate as input size N increases.
  • Hardware independent: It measures algorithm logic, not CPU clock speed.
  • Nested loops multiply: A loop inside a loop over the same input usually means O(N²).
  • Halving search space: Dividing input in half each step yields O(log N).

    • 8. Quiz

    Question 1: Why don't we measure algorithm efficiency using a clock/stopwatch? Answer: Stopwatch time depends on hardware specs, CPU load, operating system, and programming language. Time complexity measures mathematical operation growth independently of hardware.
    Question 2: If an algorithm runs in Linear Time O(N) and takes 1 second for 1,000 elements, roughly how long will it take for 10,000 elements? Answer: Roughly 10 seconds, because in linear time, scaling input size by 10x increases operation time by 10x.
    Question 3: What is the time complexity of searching an item in an unsorted list of size N? Answer: O(N) linear time, because in the worst case you must check every element up to the end.
    Question 4: What happens to a Quadratic O(N²) algorithm when the input size increases from 100 to 1,000? Answer: The operations increase by 100x (from 10,000 to 1,000,000 operations), because (10x input)² = 100x operations.
    Question 5: If a code snippet has two separate, non-nested loops that each run N times, what is the total time complexity? Answer: O(N). The operations total N + N = 2N, but constants are dropped in asymptotic analysis, resulting in linear O(N) complexity.