Algorithms Fundamentals

An algorithm is a computable set of steps that produces a desired result. The definition covers sorting cards, finding a route, and ranking search results. The same design ideas appear across many different problems. You split a problem, choose greedily, cache repeated work, or search a tree of choices.

This course gives you that vocabulary. It is not a data structures course. Arrays, lists, trees, and hash tables appear only as containers that algorithms operate on. It is not a formal complexity-analysis course either. Big-O notation appears as vocabulary, while a dedicated course covers the mathematics. Here you learn to read a method, judge its correctness, recognize its design paradigm, and compare alternatives.

Reading pseudocode

Pseudocode describes steps without committing to one programming language. It uses familiar ideas such as assignment, loops, conditions, and function calls. It leaves out syntax that does not affect the method.

function linear-search(list, target):
    for each item at index i in list:
        if item equals target:
            return i
    return not-found

You can translate the method into any suitable programming language. The program changes, but the algorithm does not.

Correctness and termination

An algorithm is correct when it produces the required result for every valid input. Passing a few tests does not establish that claim. Termination means the algorithm finishes for every valid input. A loop that never reaches its exit condition violates that requirement.

An invariant is a condition that remains true while a loop runs. A correctness argument can show that the invariant starts true, remains true after each step, and implies the result at termination.

You will not prove every algorithm you use. You should still ask two questions. Does it always stop? Does it produce the required output for every valid input?

Measuring cost without the math

Two correct algorithms can require very different amounts of work. Big-O notation describes an asymptotic upper bound. Saying a running time is O(g(n)) means that a constant multiple of g(n) bounds it once n is large enough. You will see O(n), O(n log n), and O(n²) as linear, linearithmic, and quadratic growth labels. A dedicated course covers their formal derivation.

Search: two strategies, two costs

Linear search checks items one at a time until it finds the target or runs out of items; on average it examines about half the list before finding a match. It works on any list, sorted or not.

Binary search requires a sorted array. It compares the target with the middle item, then keeps only the half that can contain the target. It stops when it finds the value or empties the interval. Repeated halving gives it O(log n) running time.

That trade — a precondition (sortedness) in exchange for a faster algorithm — is a pattern you will see across the whole field.

Sorting: same goal, different trade-offs

A sort arranges items into a predetermined order. Three classic sorting algorithms illustrate how differently "the same problem" can be solved.

Insertion sort takes each next item and inserts it among the items already placed. Its running time is O(n²) because an insertion can move many items. It works in place and performs well on partially sorted input.

Merge sort splits the input into halves, recursively sorts each half, and merges the results. It runs in Θ(n log n) time. A standard array implementation uses extra space proportional to the input size.

Quicksort picks a pivot, partitions the other items around it, and recursively sorts each partition. Its worst case is Θ(n²), but its typical running time is O(n log n). A tuned implementation often performs well in practice. Worst-case and typical cost can lead to different choices.

Design paradigms

Most algorithms you meet are an instance of a handful of reusable strategies.

Brute force tries every one of a wide range of possible solutions. It is usually the easiest approach to get correct and the slowest to run; treat it as a baseline and a fallback, not a first choice for large inputs.

Divide and conquer solves a problem directly when the instance is small enough to be easy, and otherwise splits it into smaller instances, solves each recursively, and combines the results into a solution for the original problem. Merge sort and binary search are both divide-and-conquer algorithms.

Greedy algorithms always take the best immediate, or local, choice available at each step. That local choice can build a globally optimal solution for some problems, and a merely acceptable one for others — the paradigm is fast and simple, but you have to verify it actually solves the problem you have, not assume it.

Dynamic programming stores solutions to repeated subproblems. Each distinct subproblem is solved once, then reused. It pays off when the same subproblems recur.

Backtracking finds a solution by trying one of several choices at each decision point; when a choice turns out to be wrong, computation backtracks to that decision point and tries a different choice. It is commonly implemented with recursion and amounts to a depth-first search through a tree of possible choices.

Recursion — a function calling itself on a smaller part of the same task — is the technique that makes divide and conquer, backtracking, and many dynamic programming implementations possible. It is not itself a design paradigm; it is the mechanism several paradigms are built on.

Where this course stops

You now have the vocabulary to read an algorithm description, judge its correctness informally, name the paradigm it follows, and reason about why one correct algorithm might still be the wrong choice for your data. Formal complexity analysis, the data structures these algorithms operate on, and graph-specific algorithms (shortest paths, traversal) are each large enough to be their own course — follow the links at the end of this course to continue in that order.