DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

Time Complexity (Big-O)

What Is Time Complexity?

Imagine two people are asked to find a specific name in a phone book. The first person starts from page one and reads every name until they find it. The second person opens the book in the middle, decides which half contains the name, and repeats — cutting the search area in half each time.

Both people find the name. But the second person finds it dramatically faster, especially as the phone book grows larger.

This difference in how work grows with input size is what time complexity measures.

Time complexity is not about how many seconds an algorithm takes to run. It is about how the number of operations an algorithm performs grows as the input size grows. A fast computer running a slow algorithm still loses to a slow computer running a fast one — once the input is large enough.

This is why time complexity is the most important tool you have for evaluating and comparing algorithms.

Why Time Complexity Matters

Consider two algorithms that both correctly sort a list:

›Algorithm A performs n² comparisons
›Algorithm B performs n log n comparisons

For a list of 10 elements, the difference is trivial — 100 vs 33 operations. For a list of one million elements, Algorithm A performs one trillion operations while Algorithm B performs roughly 20 million. On modern hardware, that is the difference between finishing in milliseconds and taking hours.

Choosing the wrong algorithm does not just make your code slow — it makes features impossible to ship at scale. This is precisely why every serious technical interview includes time complexity questions.

What Is Big-O Notation?

Big-O notation is the mathematical language used to describe time complexity. It expresses how the number of operations grows in relation to the input size as that input approaches very large values.

Big-O describes the worst-case upper bound — the maximum amount of work an algorithm will ever do for a given input size.

The letter O stands for "Order of magnitude." The variable n represents the size of the input.

Some rules that simplify Big-O analysis:

›Drop constants — O(2n) becomes O(n). Constants do not matter at scale.
›Drop lower-order terms — O(n² + n) becomes O(n²). The dominant term takes over as n grows.
›Worst case is the default — unless otherwise stated, Big-O refers to the worst-case scenario.

These simplifications let you focus on the fundamental growth behavior of an algorithm, not implementation details.

The Big-O Complexity Hierarchy

From fastest to slowest as input grows:

Complexity	Name	Example
O(1)	Constant	Array index access, hash map lookup
O(log n)	Logarithmic	Binary search
O(n)	Linear	Linear scan, finding max
O(n log n)	Linearithmic	Merge sort, heap sort
O(n²)	Quadratic	Bubble sort, nested loops
O(2^n)	Exponential	Recursive subset generation
O(n!)	Factorial	Brute-force permutation generation

A useful mental model: as input size doubles, O(1) stays the same, O(n) doubles, O(n²) quadruples, and O(2^n) squares itself. The gap between good and bad algorithmic choices grows explosively with input size.

O(1) — Constant Time

An algorithm runs in O(1) when it performs the same number of operations regardless of input size. It does not matter whether the array has 10 elements or 10 million — the work is always the same.

The most common example: accessing an element in an array by its index. The memory address is computed directly from the index — no searching required.

Java

Try it out

public class ConstantTime {

    // Access element by index — always one operation regardless of array size
    public static int getFirstElement(int[] arr) {
        return arr[0];
    }

    // Check if a number is even — always one operation
    public static boolean isEven(int num) {
        return num % 2 == 0;
    }

    public static void main(String[] args) {
        int[] numbers = {42, 15, 8, 93, 27};

        System.out.println("First element: " + getFirstElement(numbers));
        System.out.println("Is 42 even: " + isEven(42));
        System.out.println("Is 15 even: " + isEven(15));
    }
}

Output:
First element: 42
Is 42 even: true
Is 15 even: false

The array could have 5 elements or 5 million — arr[0] takes one step either way. That is O(1).

O(n) — Linear Time

An algorithm runs in O(n) when the number of operations grows directly proportional to the input size. If the input doubles, the work doubles.

The classic example: scanning every element in a list to find a target value or compute a result.

Java

Try it out

public class LinearTime {

    // Find the maximum element — must check every element once
    public static int findMax(int[] arr) {
        int max = arr[0];

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        return max;
    }

    // Calculate sum — must visit every element once
    public static int calculateSum(int[] arr) {
        int sum = 0;

        for (int num : arr) {
            sum += num;
        }

        return sum;
    }

    public static void main(String[] args) {
        int[] numbers = {34, 7, 23, 32, 5, 62, 15};

        System.out.println("Maximum: " + findMax(numbers));
        System.out.println("Sum: " + calculateSum(numbers));
    }
}

Output:
Maximum: 62
Sum: 178

With 7 elements, findMax performs 6 comparisons. With 70 elements, it performs 69. With 7 million, it performs ~7 million. Work grows linearly — that is O(n).

O(n²) — Quadratic Time

An algorithm runs in O(n²) when there is a loop inside a loop, and both loops depend on the input size. For every element, you do work proportional to every other element.

The classic example: Bubble Sort. For each of the n elements, it compares against up to n other elements.

Java

Try it out

public class QuadraticTime {

    // Bubble Sort — compares every pair of adjacent elements repeatedly
    public static void bubbleSort(int[] arr) {
        int n = arr.length;

        // Outer loop — controls how many passes are made
        for (int i = 0; i < n - 1; i++) {

            // Inner loop — compares adjacent elements in each pass
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] numbers = {64, 34, 25, 12, 22, 11, 90};

        System.out.print("Before: ");
        for (int num : numbers) System.out.print(num + " ");
        System.out.println();

        bubbleSort(numbers);

        System.out.print("After:  ");
        for (int num : numbers) System.out.print(num + " ");
        System.out.println();
    }
}

Output:
Before: 64 34 25 12 22 11 90
After:  11 12 22 25 34 64 90

Dry Run: Bubble Sort on [64, 34, 25, 12]

Input: [64, 34, 25, 12]

Pass 1 (i=0):
  j=0 → 64 > 34? Yes → swap → [34, 64, 25, 12]
  j=1 → 64 > 25? Yes → swap → [34, 25, 64, 12]
  j=2 → 64 > 12? Yes → swap → [34, 25, 12, 64]  ← 64 is in final position

Pass 2 (i=1):
  j=0 → 34 > 25? Yes → swap → [25, 34, 12, 64]
  j=1 → 34 > 12? Yes → swap → [25, 12, 34, 64]  ← 34 is in final position

Pass 3 (i=2):
  j=0 → 25 > 12? Yes → swap → [12, 25, 34, 64]  ← 25 is in final position

Result: [12, 25, 34, 64]
Total comparisons for n=4: 6 = (n-1) + (n-2) + (n-3) = n(n-1)/2 ≈ O(n²)

The outer loop runs n times. The inner loop runs up to n times for each outer iteration. That is n × n = n² operations in the worst case — O(n²).

O(log n) — Logarithmic Time

An algorithm runs in O(log n) when it cuts the problem size in half at each step. Even as input grows enormously, the number of operations grows very slowly.

The classic example: Binary Search on a sorted array. Instead of scanning every element, it eliminates half the remaining elements with each comparison.

Java

Try it out

public class LogarithmicTime {

    // Binary Search — eliminate half the search space at each step
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            // Find the middle index
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                // Found the target
                return mid;
            } else if (arr[mid] < target) {
                // Target is in the right half — discard the left
                left = mid + 1;
            } else {
                // Target is in the left half — discard the right
                right = mid - 1;
            }
        }

        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] sorted = {5, 12, 18, 25, 34, 47, 56, 68, 79, 91};
        int target = 47;

        int result = binarySearch(sorted, target);

        if (result != -1) {
            System.out.println(target + " found at index: " + result);
        } else {
            System.out.println(target + " not found");
        }
    }
}

Output:
47 found at index: 5

Dry Run: Binary Search for 47 in [5, 12, 18, 25, 34, 47, 56, 68, 79, 91]

Array (10 elements, indices 0-9):
[5, 12, 18, 25, 34, 47, 56, 68, 79, 91]

Step 1: left=0, right=9 → mid=4 → arr[4]=34
  34 < 47 → target is in right half → left = 5

Step 2: left=5, right=9 → mid=7 → arr[7]=68
  68 > 47 → target is in left half → right = 6

Step 3: left=5, right=6 → mid=5 → arr[5]=47
  47 == 47 → Found at index 5

Total steps: 3 (instead of 6 with linear search)
For n=10: log₂(10) ≈ 3.3 steps maximum
For n=1,000,000: log₂(1,000,000) ≈ 20 steps maximum

This is the power of O(log n). One million elements — found in at most 20 comparisons.

How to Calculate Time Complexity

When you look at code, follow these three steps:

Step 1 — Identify the loops and their relationship to n.

A single loop from 0 to n is O(n). A loop inside another loop, both from 0 to n, is O(n²). A loop that halves its range each iteration is O(log n).

Step 2 — Add complexities for sequential sections, multiply for nested ones.

If two separate loops run one after the other, the total is O(n) + O(n) = O(2n) = O(n). If one loop is nested inside another, the total is O(n) × O(n) = O(n²).

Step 3 — Keep only the dominant term and drop constants.

O(n² + n + 100) simplifies to O(n²). The n² term dominates as n grows large.

Practical Examples

int x = arr[0];                    → O(1)   one operation

for i from 0 to n:                 → O(n)   one loop
    print arr[i]

for i from 0 to n:                 → O(n²)  nested loops
    for j from 0 to n:
        print arr[i] + arr[j]

for i from 0 to n:                 → O(n)   sequential loops add
    print arr[i]                             O(n) + O(n) = O(2n) = O(n)
for j from 0 to n:
    print arr[j]

while n > 1:                       → O(log n)  halving each step
    n = n / 2

Best Case, Worst Case, and Average Case

Big-O always refers to the worst case by default, but algorithms can behave differently depending on input.

Case	Meaning	Example for Linear Search
Best Case	Minimum operations possible	Target is the first element — O(1)
Average Case	Expected operations on typical input	Target is somewhere in the middle — O(n/2) = O(n)
Worst Case	Maximum operations possible	Target is the last element or not present — O(n)

When someone asks "what is the time complexity?" in an interview, they almost always mean worst case unless they explicitly say otherwise.

Comparing Complexities at Scale

To make the growth rates concrete, here is how many operations each complexity requires as input grows:

n (input size)	O(1)	O(log n)	O(n)	O(n log n)	O(n²)	O(2^n)
10	1	3	10	33	100	1,024
100	1	7	100	664	10,000	Way too large
1,000	1	10	1,000	9,966	1,000,000	Impossible
1,000,000	1	20	1,000,000	19,931,568	10^12	Impossible

The difference between O(n) and O(n²) for one million elements is the difference between one million operations and one trillion. This is why experienced developers never stop thinking about complexity.

Input Constraints Tell You the Expected Complexity

In competitive programming and interviews, input constraints in the problem statement are hints about the expected complexity. Experienced developers use this to immediately narrow down which approach to try.

Constraint	Likely Expected Complexity
n <= 10	Any complexity works, even O(n!)
n <= 1,000	O(n²) is acceptable
n <= 100,000	O(n log n) is required
n <= 1,000,000	O(n) or O(n log n)
n <= 10^9	O(log n) or O(1)

This mental mapping lets you decide your approach before writing a single line of code. If n is one million and you are considering a nested loop, you already know it will not pass.

Common Mistakes Beginners Make

Counting exact operations instead of growth rate. Time complexity is about how work scales, not how many operations run on a specific input. O(100n) and O(n) are the same complexity — the constant 100 disappears.

Forgetting that nested loops are not always O(n²). A nested loop is O(n²) only when both loops depend on n. If the inner loop runs a fixed number of times (say, always 5 iterations), the overall complexity is still O(n).

Ignoring the worst case. A linear search that finds the target at index 0 is not O(1). Its worst-case complexity is still O(n) — which is what matters for analysis.

Confusing time complexity with actual speed. An O(n log n) algorithm can be slower than an O(n²) algorithm for very small inputs because of constants and overhead. Complexity describes scaling behavior, not raw speed on small inputs.

Treating all O(n) algorithms as equal. Two O(n) algorithms can differ by a constant factor of 100x in practice. Complexity analysis tells you scaling behavior — profiling tells you actual runtime.

Interview Questions

Q: What is time complexity, and why does it matter?

Time complexity measures how the number of operations an algorithm performs grows as input size increases. It matters because the right algorithm can handle a million elements in milliseconds while the wrong one takes hours. Choosing based on time complexity is one of the core skills of software engineering.

Q: What does Big-O notation represent?

Big-O describes the worst-case upper bound on how an algorithm's operation count grows with input size. It drops constants and lower-order terms to focus on the fundamental growth behavior — O(2n + 5) becomes O(n), O(n² + n) becomes O(n²).

Q: What is the time complexity of binary search, and why?

Binary search is O(log n). At each step, it eliminates half the remaining search space. Starting with n elements, after one step you have n/2, then n/4, then n/8. The number of steps needed to reduce n to 1 is log₂(n).

Q: How do you calculate the time complexity of code with nested loops?

If both loops run from 0 to n, the time complexity is O(n²). In general, nested loops multiply their complexities: an outer O(n) loop containing an inner O(n) loop gives O(n × n) = O(n²). Sequential (non-nested) loops add: O(n) + O(n) = O(2n) = O(n).

Q: What is the difference between best case, worst case, and average case?

Best case is the minimum work for a given input (e.g., target found at index 0 in linear search — O(1)). Worst case is the maximum work (target not found — O(n)). Average case is the expected work on typical inputs. Interviews default to worst case unless explicitly stated otherwise.

FAQs

Is a lower time complexity always better?

Not always. O(n log n) algorithms often have more overhead than O(n²) algorithms for very small inputs. If your data is always small (under 50 elements), a simple O(n²) solution may be faster in practice due to lower constant factors and simpler logic. Use complexity analysis for large inputs, profiling for real performance decisions.

Why do we drop constants in Big-O?

Because constants are implementation details, not fundamental properties of the algorithm. O(2n) and O(100n) both grow linearly — as n approaches infinity, the constant factor becomes irrelevant compared to the growth rate. Dropping constants lets us compare algorithms at a conceptual level.

Can the same algorithm have different complexities for different inputs?

Yes. This is the difference between best case, average case, and worst case. Quick Sort is O(n log n) on average but O(n²) in the worst case (when the pivot is always the smallest or largest element). This is why algorithm analysis considers all three scenarios.

What is the time complexity of built-in language functions?

It depends on the function and language. Java's ArrayList.get(i) is O(1). Java's ArrayList.remove(value) is O(n). Python's list.append() is O(1) amortized. Python's in operator on a list is O(n) but on a set is O(1). Always check the documentation or know the underlying data structure.

Quick Quiz

Question 1: What is the time complexity of accessing the last element of an array by index?

›A) O(n)
›B) O(log n)
›C) O(n²)
›D) O(1)

Answer: D) O(1). Array index access is always constant time regardless of position or array size. The memory address is computed directly from the index.

Question 2: A function has an outer loop running n times and an inner loop running n times. What is the time complexity?

›A) O(n)
›B) O(2n)
›C) O(n²)
›D) O(n log n)

Answer: C) O(n²). Nested loops multiply their complexities. O(n) × O(n) = O(n²). The work grows quadratically as input grows.

Question 3: Binary search requires a sorted array. What is its worst-case time complexity?

›A) O(n)
›B) O(n²)
›C) O(log n)
›D) O(1)

Answer: C) O(log n). Binary search eliminates half the remaining elements at each step. For n elements, the maximum number of steps is log₂(n) — roughly 20 steps even for one million elements.

Question 4: Which of the following simplifications is correct?

›A) O(n² + n) = O(n)
›B) O(3n) = O(n³)
›C) O(n² + n) = O(n²)
›D) O(n + log n) = O(log n)

Answer: C) O(n² + n) = O(n²). Always keep the dominant (fastest-growing) term and drop the rest. As n grows, n² grows far faster than n, making the n term irrelevant.

Summary

Time complexity measures how the number of operations an algorithm performs grows as input size increases. Big-O notation expresses this growth rate in its worst-case, simplified form.

The key ideas to carry forward:

›Time complexity is about growth rate, not exact operation count
›Drop constants and lower-order terms — only the dominant term matters
›O(1) is constant, O(log n) is logarithmic, O(n) is linear, O(n²) is quadratic
›Nested loops multiply complexities; sequential loops add them
›Input constraints in interview problems are hints about the expected complexity
›Worst case is the default — unless best or average is explicitly asked for

In the next topic, you will explore Space Complexity — learning how to measure and reason about the memory an algorithm uses as input grows.

←

PreviousWhat is an Algorithm?

NextSpace Complexity

→