I'd like to get a sense for the range of complexity that algorithms fall into. I think it would be interesting and helpful for those, like me, trying to better understand how algorithms are formulated and how to deconstruct them.

Can you offer a basic algorithm with explanation, an intermediate algorithm with explanation, and maybe an expert level one (with or without) an explanation?


3 Answers 3


From the Programmer Competency Matrix:

Basic sorting, searching and data structure traversal and retrieval algorithms

Tree and Graph data structures, simple greedy and divide and conquer algorithms.

graph algorithms, numerical computation algorithms, etc.

  • These seem to be pitched somewhat lower than the ones in other answers.
    – Eliot Ball
    Aug 30, 2012 at 11:25


Binary Search: Locates the position of an item in a sorted array.

AVL Tree Insertion: Insert an item in a AVL tree maintaining the subtree balancing property.

Depth-first Search, Breadth-first Search: Walk over the nodes of a Graph in DFS or BFS order.


Dijkstra's Algorithm: Graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree.

Longest Common Subsequence: Find the longest subsequence common to all sequences in a set of sequences (often just two).

Convex Hull (Graham Scan): Given a set of points, find the minimum subset of those points to cover with a convex polygon.

Counting Sort: Sorting algorithm of consecutive integers in O(n).


Range Minimu Query: Given an array A[1,n] of n ordered objects (such as numbers), a Range Minimum Query (or RMQ) from i to j asks for the position of a minimum element in the sub-array A[i,j]. RMQs can be used to solve the lowest common ancestor problem.

  • 3
    I agree in general, but I'd say that a counting sort is far easier than AVL tree insertion. Sep 19, 2011 at 7:00

Some more examples

Beginner: Linked list reversal, Mergesort, Sieve of Eratosthenes, Red-black tree algorithms (insertion and removal)

Intermediate: Simplex, Miller-Rabin primality test, Huffman coding, Kruskal's algorithm

Advanced: Viterbi Algorithm, Cooley–Tukey FFT, Simulated Annealing, Hindley–Milner type inference

I tried to find links that had at least some pseudocode and/or good explanation. But the thing about advanced algorithms is that they have many variations. So, you can explain the basic outline of a "genetic algorithm", but there are actually many algorithms that goes by that name. (The same for the FFT; I linked a named variant of it)

This text about numerical integration, for a gaming audience, describes two algorithms for numerical integration: a simpler, straightforward algorithm (the Euler integrator), and a more advanced one (the Runge-Kutta order 4 integrator). It may be a good for seeing "basic vs. advanced". You can use integrators for simulating physics, and the Euler integrator leads to enormous errors, so he recommends RK4 instead. But they are arguably variations of the "same" algorithm: Euler is first-order RK.

Not the answer you're looking for? Browse other questions tagged or ask your own question.