How do you get various algorithm analysis factors in your code?

Question

I am attempting to prepare a presentation to explain the basics of algorithm analysis to my co-workers - some of them have never had a lecture on the subject before, but everyone has at least a few years programming behind them and good math backgrounds, so I think I can teach this. I can explain the concepts fine, but I need concrete examples of some code structures or patterns that result in factors so I can demonstrate them.

Geometric factors (n, n^2, n^3, etc) are easy, embedded loops using the same sentinel, but I am getting lost on how to describe and show off some of the less common ones.

I would like to incorporate exponential (2^n or c^n), logarithmic (n log(n) or just log(n)) and factoral (n!) factors in the presentation. What are some short, teachable ways to get these in code?

Answer 1

A divide-and-conquer algorithm that does a constant amount of work for each time it divides the problem in half is O(log n). For example a binary search.

A divide-and-conquer algorithm that does a linear amount of work for each time it divides the problem in half is O(n * log n). For example a merge sort.

Exponential and factorial are probably best illustrated by iterating respectively over all subsets of a set, or all permutations of a set.