Postgraduate tutorial

Big-O Notation and Time Complexity

Learn how to describe algorithm efficiency with Big-O, from O(1) to O(n²), with Python examples.

  • Postgraduate
  • 2 min read
  • Free

Big-O notation describes how an algorithm’s running time (or memory) grows as the input size n grows, ignoring constants and smaller terms.

Common complexities

Big-ONameExample
O(1)ConstantReading an array element by index
O(log n)LogarithmicBinary search in a sorted list
O(n)LinearScanning a list once
O(n log n)LinearithmicMerge sort
O(n²)QuadraticComparing every pair with nested loops

Example: finding duplicates

# O(n²): compare every pair
def has_duplicate_slow(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

# O(n): remember what you've seen in a set
def has_duplicate_fast(items):
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

For a million items, the first version can make about 500 billion comparisons. The second makes about a million set lookups.

Rules of thumb

  • Drop constants: O(2n) is O(n).
  • Keep the dominant term: O(n² + n) is O(n²).
  • Loops in sequence add; nested loops multiply.

Practice

What is the complexity of a loop that halves n until it reaches 1?

O(log n), because the number of halvings is about log₂ n.

Want a live class on this?

An advisor will call you within one business day to recommend a course and a batch that fits your schedule.

  1. An advisor calls you within one business day.
  2. You talk through your background and goals for about 20 minutes.
  3. You get a recommended program and batch, with no obligation to enroll.
info@stratedgeitconsulting.com +1 (302) 434-8889 ext. 101 Monday to Saturday, 9 AM to 7 PM ET

Tell us about you

Takes about a minute. Fields marked optional can be skipped.

Enter your full name.
Enter an email address like name@example.com.
Enter a phone number so an advisor can call you.
Choose what you’re interested in.
Preferred batch
Tick the box so an advisor can contact you.

We use these details as described in our Privacy Policy. By submitting, you agree to our Terms and Conditions.