What Is an Algorithm?

The Pasta Story

Imagine you're cooking pasta for the very first time. You search online and find a recipe:

1. Boil 4 cups of water
2. Add a pinch of salt
3. Add 100g of pasta
4. Cook for 8–10 minutes, stirring occasionally
5. Drain and serve

This recipe is an algorithm. It's a step-by-step set of instructions that, when followed precisely, produces the same result every time — regardless of who follows it.

Now imagine cooking that same pasta for 1000 people. Suddenly, the recipe isn't enough. You need to think about how many pots, how to coordinate timing, which steps can happen in parallel. A good algorithm doesn't just work for one case — it scales.

That's the essence of what computer scientists care about. Not just "does it work?" but "does it still work when the input is 10x, 100x, or 1,000,000x bigger?"

Formal Definition

An algorithm is a finite sequence of well-defined instructions that solves a class of problems and produces a correct output for every valid input.

The key word is class. A sorting algorithm doesn't sort one specific list — it sorts any list. A pathfinding algorithm doesn't find one route — it finds the shortest path in any graph.

Five Properties Every Algorithm Must Have

Vague Instruction vs. Real Algorithm

Vague instruction:

"Sort these numbers: 5, 2, 8, 1"

This tells you what to do but not how. A computer cannot execute this.

Real algorithm (Bubble Sort outline):

1. Start at the beginning of the list
2. Compare the first and second element
3. If the first is greater than the second, swap them
4. Move to the next pair and repeat step 3
5. After one pass, the largest element is at the end
6. Repeat steps 1–5 for the remaining unsorted portion
7. Stop when no swaps occur in a full pass

This is unambiguous. Every step is executable. It terminates. It works on any list.

Euclid's GCD — One of History's Oldest Algorithms (300 BC)

The ancient Greek mathematician Euclid described an algorithm for finding the Greatest Common Divisor of two numbers around 300 BC. It's still used today.

The insight: The GCD of two numbers doesn't change if you replace the larger number with its remainder when divided by the smaller.

def gcd(a, b):
    # Base case: if b is 0, GCD is a
    while b != 0:
        a, b = b, a % b   # Replace a with b, b with remainder of a/b
    return a

# Example usage
print(gcd(48, 18))   # Output: 6
print(gcd(100, 75))  # Output: 25

Trace for gcd(48, 18):

Step 1: a=48, b=18  → new a=18, new b=48%18=12
Step 2: a=18, b=12  → new a=12, new b=18%12=6
Step 3: a=12, b=6   → new a=6,  new b=12%6=0
Step 4: b=0, return a=6

Output: 6

This algorithm runs in O(log(min(a,b))) time — extraordinarily fast. A 2300-year-old idea, still in every modern math library.

Algorithm vs. Program

These two words are often confused. They are not the same thing.

An algorithm is the idea. A program is the implementation.

The same algorithm can be implemented in dozens of programming languages. The algorithm itself doesn't care about syntax — it's a logical plan.

Problem → Algorithm → Data Structure

Algorithms and data structures are partners. You almost never choose one without thinking about the other.

The right algorithm applied to the wrong data structure can be 1000x slower than the right combination.

Algorithms in the Real World

Algorithms aren't just academic exercises. They power the digital world:

• Google's PageRank — ranks billions of web pages by analyzing the link graph. Without it, Google Search wouldn't exist.
• GPS routing — Dijkstra's and A* algorithms find your shortest path in milliseconds across millions of road segments.
• Search engines — inverted index algorithms allow full-text search across trillions of documents.
• Netflix recommendations — collaborative filtering algorithms predict what you'll want to watch.
• Encryption — RSA relies on the difficulty of factoring large numbers — an algorithmic hardness assumption.

Correctness vs. Efficiency — Both Matter

There are two questions to ask about any algorithm:

1. Is it correct? Does it always produce the right answer for every valid input? An algorithm that usually works but sometimes fails is not an algorithm — it's a bug.

2. Is it efficient? Does it run fast enough, and use acceptable memory, even for large inputs?

A correct but slow algorithm is usable for small inputs. An efficient but incorrect algorithm is useless. You need both.

In this course, we'll study algorithms from both angles — proving they work, and analyzing how fast they work as inputs grow.

Key Takeaways

• An algorithm is a finite, unambiguous, terminating set of instructions that solves a problem for any valid input
• It has five essential properties: Input, Output, Definiteness, Finiteness, Effectiveness
• An algorithm is not a program — it's the idea behind the program
• Algorithms and data structures work together — choosing the right pair is a core skill
• Every major technology — search, navigation, encryption, recommendations — is built on algorithms
• The two measures of an algorithm's quality: correctness and efficiency

In the next lesson, we'll learn exactly how to measure efficiency — using Big O notation.