Algorithmic problem with many different time/space complexity solutions

Question

I am preparing a lesson about algorithmic thinking for beginner programmers. I would like to show them an easy to understand problem which has as many solutions as possible with different time or space complexities. Sorting quickly comes to mind but if you avoid intentionally stupid solutions such as Bogosort, you only really have O(n^2) and O(n*log n) complexities.

In this respect I love the problem for computing the n-th Fibonacci number with integer arithmetic. You can do it exponentially as a naive approach, linearly if you are a bit clever, and even logarithmically if you are smart as hell. On the other hand, fibonacci numbers would not appear very practical to novice programmers. I would like something that is related to more practical problems as I do not want the students to think that algorithm design is something really abstract and theoretical.

Answer 1

I like this one: given a string $S$, find the longest substring that appears two or more times in $S$.

There are plausible algorithms with running time $O(n^3)$, $O(n^2)$, $O(nk \log n)$, $O(nk \log k)$, $O(nk)$, $O(n \log n)$, $O(n \log k)$, and even $O(n)$, where $n$ is the length of $S$ and $k$ is the length of the longest such substring.

However I don't know if it has practical applications.

Computational biology is a good source of practical algorithm problems.

Answer 2

Another example is the famous subset sum problem: There is an exponential-time algorithm that works in $O(2^{n/2} \textsf{poly}(n))$. There are also pseudopolynomial time algorithms working in $O(nt)$ (via dynamic programming) and $O(n+t)$ (the later one being a randomized algorithm). Depending on the input size, one can choose between different algorithms (e.g. if $t$ is too large, then maybe the exponential-time algorithm works better).