📊 We use cookies & analytics to improve your experience. Learn more
Latest

Interview DSA Crash Course Module 1 · Lesson 1 of 15

0% Exit to course

Module 1 · Complexity and how to think out loud Lesson 1 of 15

Big-O without the fear

Learning objective

Big-O describes how work grows as input grows. A loop inside a loop over the same list is O(n²) — that is most of what a fresher interview needs.

The concept

Big-O is a way of saying how the work grows when the input grows, ignoring constants. Looking up a value in a list of n items takes up to n steps — that is O(n). Reading arr[5] takes one step whatever the size — O(1). A loop inside a loop is O(n²), and that is the one that quietly fails an interview.

You do not need proofs. You need to look at your own code and count the loops: none or one pass is fine, a nested loop over the same input is a warning, and a nested loop over the WHOLE input inside another is usually the thing to fix. Say the number out loud in an interview and you have answered the question they were about to ask.

Python
# O(1) - one step, any size
def first(items): return items[0]

# O(n) - one pass
def total(items): return sum(items)

# O(n^2) - a loop inside a loop over the same input
def has_pair(items):
    for a in items:
        for b in items:
            if a + b == 0:
                return True
    return False

# Hidden O(n): items.index(x) scans. Sorting is O(n log n).

Common mistakes

The mistake is assuming a clever-looking solution is fast. list.index(x) reads as one call and is a hidden O(n) scan; sorting is O(n log n) and turns many O(n²) double loops into a single pass. Learn the cost of the five operations you actually use, and you will spot most bad solutions before you write them.

Worked example

A single pass to find the maximum is O(n); checking whether a list has duplicates by comparing every pair is O(n²); a set makes it O(n) — same answer, different cost.

Your practice task

For five problems you have already solved, write the time and space complexity of each in one line.

Do this before moving on. Reading a solution teaches the shape of it; typing it teaches you.

Key takeaway

Big-O is a way of saying how the work grows when the input grows, ignoring constants.

Create free account or sign in

Almost there

15 lessons left of 15

Finish every lesson to unlock the certificate. Each one ends in a practice task — do them and the final project brief writes itself.