Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

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.

share|improve this answer
+1 (when I get votes) for the PCM. – Josh K Dec 13 '10 at 18:54
These seem to be pitched somewhat lower than the ones in other answers. – Eliot Ball Aug 30 '12 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.

share|improve this answer
+1 to let you post links.... – FabienAndre Dec 13 '10 at 16:50
@FabienAndre: Thanks! – vz0 Dec 13 '10 at 17:11
I agree in general, but I'd say that a counting sort is far easier than AVL tree insertion. – Viktor Dahl Sep 19 '11 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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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