# Algorithmic problem with many different time/space complexity solutions

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.

• Perhaps better on Computer Science Educators? If you choose to ask it there, please delete the question here to prevent duplicates. – Yuval Filmus Apr 1 at 11:57
• You may want to look for solutions featuring the lowest time complexity for a given space complexity and vice versa: no strictly better or worse. – greybeard Apr 1 at 15:53

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.
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).