DSA Interview Question

What is Big O notation?

Updated 2026-08-16 · Beginner friendly

Quick answer

Big O notation describes how the running time or memory of an algorithm grows as the input gets larger. It focuses on the worst case and ignores constants, so it captures the overall trend rather than exact timings. For example O(n) means the work grows in line with the input size, and O(1) means the work stays constant no matter the size.

Key takeaways

Big O describes how runtime or memory grows as the input grows, ignoring constants and focusing on the worst case.
Common orders from fast to slow are O(1), O(log n), O(n), O(n log n), O(n squared), and O(2 to the n).
State both time and space complexity when you finish a solution, even if the interviewer does not ask.

Why we use it

Two algorithms can both solve a problem, but one may be far slower on large inputs. Big O gives us a simple language to compare them without depending on the machine or the programming language.

Common complexities from fast to slow

O(1): constant time, such as reading an array element by index.
O(log n): logarithmic, such as binary search.
O(n): linear, such as scanning a list once.
O(n log n): common for good sorting algorithms.
O(n squared): nested loops over the same data.
O(2 to the n): exponential, very slow, seen in brute force recursion.

// O(n): one loop over n items
for (int x : items)
    cout << x << endl;

// O(n squared): a loop inside a loop
for (int a : items)
    for (int b : items)
        cout << a << " " << b << endl;

// O(n): one loop over n items
for (int x : items)
    System.out.println(x);

// O(n squared): a loop inside a loop
for (int a : items)
    for (int b : items)
        System.out.println(a + " " + b);

# O(n): one loop over n items
for x in items:
    print(x)

# O(n squared): a loop inside a loop
for a in items:
    for b in items:
        print(a, b)

In the interview

Always state the time and the space complexity when you finish a solution, even if the interviewer does not ask. Saying this runs in O(n) time and O(1) extra space shows maturity and often earns extra credit.

Frequently asked questions

Why does Big O ignore constants?

Big O captures how an algorithm scales, not its exact speed. On large inputs the growth rate dominates, so a constant factor like 2n and n both count as O(n).

What is the most common time complexity in interviews?

O(n) and O(n log n) come up most often, since many problems are solved with a single pass or an efficient sort. O(1) hash lookups also appear constantly.

Is a lower Big O always faster?

Not for small inputs. Big O describes large input behaviour, so an O(n squared) solution can beat an O(n log n) one on tiny data because of lower overhead.

Common follow up questions

What is the difference between time and space complexity? What does O(log n) mean in plain words? What is the difference between best, average, and worst case?

Want the full DSA guide?

Read every DSA concept with notes, diagrams, and code in one place. Track your progress as you go.

Open the DSA guide All DSA questions