algorithmen

Algorithms

In short: An unambiguous, step-by-step set of instructions for solving a problem — independent of a specific programming language, but the basis for any actual program code.

In more detail: Algorithms are usually compared by their efficiency (how strongly the time/memory needed grows with input size) — well-known examples are sorting and search algorithms. The choice of the right data structure often has at least as much influence on performance as the algorithm itself.

In Depth

For something to count as an algorithm, it has to satisfy three properties: it has to be unambiguous (every step is clear, no room for interpretation), finite (it terminates at some point, see the exit condition for recursion), and effective (every step is actually executable).

The efficiency of an algorithm is usually described with “Landau notation” (Big-O), which indicates how the runtime scales with growing input size n:

O(1)       - constant: accessing an array element by index
O(log n)   - logarithmic: binary search in a sorted list
O(n)       - linear: iterating through a list once
O(n log n) - e.g. efficient sorting algorithms (merge sort, quicksort)
O(n²)      - quadratic: nested loop over the same list (bubble sort)

A classic example that shows the difference between two algorithms for the same problem — searching for a value:

# Linear search: O(n), works on unsorted data
def linear_search(list_, target):
    for i, value in enumerate(list_):
        if value == target:
            return i
    return -1
 
# Binary search: O(log n), but needs a SORTED list
def binary_search(list_, target):
    left, right = 0, len(list_) - 1
    while left <= right:
        middle = (left + right) // 2
        if list_[middle] == target:
            return middle
        elif list_[middle] < target:
            left = middle + 1
        else:
            right = middle - 1
    return -1

For small inputs (few elements), the difference between O(n) and O(log n) practically doesn’t matter — for millions of entries, it’s the difference between milliseconds and noticeable wait times. This is why algorithmic thinking is especially worthwhile where amounts of data can grow, not for every single snippet of code.

In practice, you rarely have to develop algorithms completely from scratch — most standard problems (sorting, searching, shortest paths in graphs) are already efficiently implemented in standard libraries. More important than memorising specific algorithms is understanding WHY one approach is faster than another, in order to pick the right library function or data structure for your own situation.

Time vs. space complexity

Big-O usually describes time complexity (how many computational steps), but space complexity (how much additional memory is needed) is just as important — the two are often in conflict with each other (a “time-space trade-off”). An algorithm that caches intermediate results (memoization, see Recursion) trades memory usage for computation time: the Fibonacci sequence computed naively-recursively is O(2ⁿ) in time, but with a simple cache of already-computed values it becomes O(n) time at the cost of O(n) additional memory.

Greedy vs. dynamic programming

Two common algorithmic strategies solve optimisation problems very differently:

• Greedy: makes the locally best decision at every step, without considering later consequences — fast and simple to implement, but doesn’t always deliver the globally best result (e.g. for the coin-change problem with unfavourable coin denominations).
• Dynamic programming: breaks the problem down into overlapping subproblems and stores their solutions, so as not to recompute them multiple times — guaranteed to deliver the optimal solution, but more complex to design and needs more memory.

# Greedy: pick the largest fitting coin at every step
# works for standard currency (1,2,5,10,20,50), but not for every set of coins
change_greedy(amount, coins_sorted_descending)
 
# Dynamic programming: compute all sub-amounts once and reuse them
change_dp(amount, coins)  # guaranteed optimal, more effort

Stability in sorting algorithms

An often overlooked detail in sorting algorithms: stability means that elements with the same sort key keep their original order relative to each other. This matters, for example, when sorting first by last name, then by first name — an unstable sort could scramble the last-name sorting during the second sort pass. Merge sort is inherently stable, quicksort in its classic form is not.

Practical impact in numbers

The difference between complexity classes isn’t an academic game: for 1 million entries, an O(n²) algorithm (e.g. bubble sort) needs on the order of 10¹² operations, while an O(n log n) algorithm (merge sort), by contrast, needs only about 2×10⁷ — a factor of roughly 50,000. This is exactly why seemingly harmless nested loops over large amounts of data (e.g. “for each element, search through the whole list”) often only become noticeably slow with real production data, even though they ran completely unremarkably in tests with few entries.

See also: Sorting, Data Structures, Recursion