DSA Tutorial #11: Big O Notation — Time and Space Complexity Explained

Every coding interview expects you to analyze your solution’s efficiency. When the interviewer asks “What is the time complexity?” they want you to use Big O notation. In this article, you will learn what Big O is, how to calculate it from code, and how to compare different complexities.

We show every example in Kotlin, Python, and Go.

What is Big O Notation?

Big O notation describes how an algorithm’s running time or space usage grows as the input size increases. It gives you the upper bound — the worst case scenario.

When we say an algorithm is O(n), we mean: as the input size n doubles, the running time roughly doubles too. We ignore constants and lower-order terms because we care about the growth rate, not the exact number of operations.

Why we ignore constants:

• O(2n) is the same as O(n) — both grow linearly
• O(n + 100) is the same as O(n) — the constant 100 becomes irrelevant for large n
• O(3n^2 + 5n + 7) is O(n^2) — the n^2 term dominates

Common Complexities

Here are the most common Big O complexities, from fastest to slowest:

For reference: if n = 1,000,000 (one million):

• O(1): 1 operation
• O(log n): ~20 operations
• O(n): 1,000,000 operations
• O(n log n): ~20,000,000 operations
• O(n^2): 1,000,000,000,000 operations (too slow)
• O(2^n): impossible (the universe ends first)

How to Calculate Big O from Code

Follow these rules to analyze any piece of code.

Rule 1: Loops

A single loop over n elements is O(n).

Python:

# O(n) — one loop through all elements
def find_max(nums):
    result = nums[0]
    for num in nums:       # runs n times
        if num > result:
            result = num
    return result

Kotlin:

// O(n) — one loop through all elements
fun findMax(nums: List<Int>): Int {
    var result = nums[0]
    for (num in nums) {    // runs n times
        if (num > result) {
            result = num
        }
    }
    return result
}

Go:

// O(n) — one loop through all elements
func findMax(nums []int) int {
    result := nums[0]
    for _, num := range nums { // runs n times
        if num > result {
            result = num
        }
    }
    return result
}

Rule 2: Nested Loops

Nested loops multiply. A loop inside a loop is O(n * n) = O(n^2).

Python:

# O(n^2) — nested loops
def has_duplicate_pair(nums):
    for i in range(len(nums)):          # runs n times
        for j in range(i + 1, len(nums)):  # runs up to n times
            if nums[i] == nums[j]:
                return True
    return False

Rule 3: Sequential Code

Sequential blocks add. O(n) + O(n) = O(2n) = O(n). O(n) + O(n^2) = O(n^2) because we keep the dominant term.

Python:

# O(n) + O(n^2) = O(n^2)
def process(nums):
    # First loop: O(n)
    total = sum(nums)

    # Nested loop: O(n^2)
    for i in range(len(nums)):
        for j in range(len(nums)):
            print(nums[i], nums[j])

Rule 4: Halving the Input

If you cut the input in half each step, it is O(log n). Binary search is the classic example.

Python:

# O(log n) — input halves each iteration
def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Rule 5: Recursive Functions

For recursive functions, count how many times the function calls itself and how much work each call does.

Python:

# O(2^n) — two recursive calls per level
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# O(n) — one recursive call per level
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

Space Complexity

Space complexity measures how much extra memory your algorithm uses. It does not count the input itself — only the additional space.

Python:

# O(1) space — only uses a few variables
def find_max(nums):
    result = nums[0]
    for num in nums:
        result = max(result, num)
    return result

# O(n) space — creates a new list
def double_values(nums):
    result = []
    for num in nums:
        result.append(num * 2)
    return result

Kotlin:

// O(1) space — constant extra memory
fun findMax(nums: List<Int>): Int {
    var result = nums[0]
    for (num in nums) {
        result = maxOf(result, num)
    }
    return result
}

// O(n) space — new list of size n
fun doubleValues(nums: List<Int>): List<Int> {
    return nums.map { it * 2 }
}

Go:

// O(1) space — constant extra memory
func findMax(nums []int) int {
    result := nums[0]
    for _, num := range nums {
        if num > result {
            result = num
        }
    }
    return result
}

// O(n) space — new slice of size n
func doubleValues(nums []int) []int {
    result := make([]int, len(nums))
    for i, num := range nums {
        result[i] = num * 2
    }
    return result
}

Best Case, Average Case, Worst Case

Most algorithms behave differently depending on the input:

In interviews, assume worst case unless told otherwise. When someone asks “What is the time complexity?” they usually mean the worst case.

Amortized Analysis

Some operations are usually fast but occasionally slow. Amortized analysis averages the cost over a sequence of operations.

The classic example is a dynamic array (ArrayList, Python list, Go slice). Appending is usually O(1), but when the array is full, it must resize (copy all elements to a new, bigger array). That resize is O(n). But it happens so rarely that the average cost per append is still O(1).

This is called amortized O(1) — each individual operation might be O(n), but over many operations, the average is O(1).

Big O of Data Structure Operations

Here is the complete reference table for all data structures covered in this series:

*Linked list insert/delete is O(1) only if you already have a reference to the node. Finding the node is O(n).

m = length of the string (for tries).

Analyzing Recursive Functions: The Recursion Tree Method

For complex recursive functions, draw a recursion tree.

Example: Merge Sort

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # T(n/2)
    right = merge_sort(arr[mid:])   # T(n/2)
    return merge(left, right)       # O(n)

Recursion tree:

• Level 0: 1 problem of size n, O(n) work
• Level 1: 2 problems of size n/2, O(n) total work
• Level 2: 4 problems of size n/4, O(n) total work
• …
• Level log n: n problems of size 1

Total: O(n) work per level * O(log n) levels = O(n log n).

Common Mistakes

1. Forgetting hidden loops. The in operator on a list is O(n) in Python, not O(1). Use a set for O(1) membership testing.

2. Ignoring the cost of string concatenation. In Python and Kotlin, strings are immutable. Concatenating n strings in a loop is O(n^2) because each concatenation creates a new string. Use "".join() or StringBuilder instead.

3. Saying O(n) when it is O(n * m). If your function has two different inputs (like two arrays of different sizes), use different variables.

# This is O(n * m), not O(n^2)
def find_common(list1, list2):
    for item in list1:         # n items
        if item in list2:      # m items (linear search)
            return True
    return False

4. Confusing O(log n) and O(n). Binary search is O(log n) because it halves the search space. A for loop from 1 to n is O(n). They are very different for large n.

5. Premature optimization. O(n^2) with small n (say n < 100) is often fast enough. Do not make code harder to read for a constant factor improvement. Optimize when n is large.

Interview Tips

When the interviewer asks about complexity:

1. State both time and space complexity. “This solution is O(n) time and O(1) space.”
2. Explain your reasoning. “The loop runs n times, and each operation inside is O(1).”
3. Mention trade-offs. “I could reduce time to O(n) by using a hash set, but that adds O(n) space.”
4. Know the optimal complexity for common problems. Sorting is at best O(n log n) with comparison-based sorts. You cannot do better unless you use counting sort.

Practice Problems

What’s Next?

Now that you can analyze complexity, it is time to learn the algorithms themselves. In the next article, you will learn Sorting Algorithms — including merge sort, quick sort, and when to use each one.

Next: DSA Tutorial #12: Sorting Algorithms

Full series: DSA from Zero to Interview Ready