Big-O the Easy Way

Beginner · 16 min read · DSA Without Fear, The Toolkit

Count loops, not symbols — and read the constraints to know which complexity the problem wants.

Big-O notation looks like maths, which is why it scares people. It isn't maths in any deep sense. It answers one practical question: if the input gets 10 times bigger, roughly how much longer does my code take? You can answer that by counting loops.

What Big-O actually says

Big-O describes how the amount of work grows with the input size n, ignoring constant factors and small terms. "This is O(n)" means "double the input, roughly double the work". "This is O(n²)" means "double the input, roughly four times the work".

Counting rules (all you really need)

1. Sequential steps add; keep the biggest.

The trick: read the constraints first

Interview problems (and online judges) usually state the input limits — "1 ≤ n ≤ 10⁵". A rough budget is about 10⁸ simple operations for a solution to run in time. Divide, and you know which complexity the problem expects:

Space complexity

Space counts the extra memory your algorithm uses, beyond the input.

Hidden costs in Java

Some lines look like O(1) but aren't:

Best, average, worst — and amortised

Interview questions

  • What is the time complexity of a loop with a while loop inside it that moves a left pointer forward?
  • Why is recursive Fibonacci slow, and what is its complexity?
  • The constraints say n ≤ 10⁵. What complexity should you aim for?

Further reading

Key takeaways

  • Big-O = how work grows with input size: count loops, multiply nested ones, halving gives log n.
  • A pointer that only moves forward makes nested-looking code O(n) (amortised).
  • Read the constraints: n ≤ 10⁵ → aim for O(n log n) or O(n); n ≤ 20 → subsets are fine; budget about 10⁸ operations.
  • Space includes the recursion stack.
  • Beware hidden costs: string concatenation in loops, list.contains, list.remove(0).

Previous: A Framework for Any Problem · Next: Recursion Without Fear