Introduction to DSA & Big-O

Two programs solve the exact same problem and print the exact same answer. One finishes before you blink. The other would still be running when the sun burns out. What’s different about them?

It isn’t the language, the hardware, or the programmer’s typing speed. It’s the algorithm and the data structure underneath — and the gap between “instant” and “never” is what this entire course is about. Today we build the vocabulary to measure that gap.

The idea: organization + instructions

Two concepts, two everyday analogies.

Data structure = how you organize your kitchen. The container you choose decides what’s easy and what’s painful:

• Tupperware containers → Arrays (fixed size, instant index access)
• A stack of plates → Stacks (last in, first out)
• The line at Starbucks → Queues (first in, first out)
• A family tree → Trees (hierarchy)
• A city map → Graphs (connections)

Algorithm = a recipe. A precise set of steps that produces a result — “find a user in a database,” “sort these names,” “bake a cake.” The same ingredients (data) with a better recipe (algorithm) can be dramatically faster.

The whole craft is matching the right structure to the right recipe so the work stays cheap as the data grows. To talk about “cheap as it grows,” we need one more tool.

Big-O: the language of scaling

Big-O notation describes the worst-case growth rate of an algorithm’s running time as the input size n grows. It deliberately ignores constants and hardware — it answers one question: when the input gets 10× bigger, what happens to the work?

See it: counting operations

Don’t trust the table — count the work yourself. This runs a single loop (O(n)) and a nested loop (O(n²)) and prints how many operations each does. Watch the quadratic column explode while the linear one crawls:

def linear(n):
  ops = 0
  for i in range(n):
      ops += 1            # one pass over the input
  return ops

def quadratic(n):
  ops = 0
  for i in range(n):
      for j in range(n):
          ops += 1        # work for every PAIR of elements
  return ops

for n in [10, 100, 1000]:
  print("n=%-5d  O(n): %-8d  O(n^2): %d" % (n, linear(n), quadratic(n)))

At n=1000, the linear version does 1,000 operations; the quadratic version does 1,000,000. Same problem size — a 1000× difference in work.

What makes it quadratic? Recall it.

Cover the comment and fill in the missing line. What single piece of structure turns linear work into O(n²)?

def quadratic(n):
  ops = 0
  for i in range(n):
      # ??? the one line that makes this O(n^2)
          ops += 1
  return ops

The tell is the nested loop: an O(n) loop running inside another O(n) loop does n × n work. Spotting nesting like this is how you eyeball complexity at a glance.

Quick check

This is Day 1 — the foundation the other 29 days stand on. Every structure and algorithm ahead will be judged by the Big-O language you just learned. Next: Day 2 — Arrays & Strings, where you’ll meet the simplest structure of all and see exactly why its O(1) indexing (and O(n) insertion) shapes everything built on top of it.