How to write a recursive function that with certain time complexity

I'm now doing exam revision, and from some past year exam papers, I noticed some questions that ask to write a recursive method with signature like

public void run(int n)

that must have a time complexity of like : $O(n^2), O(n^3), O(n^7), O(n^2!), O(2^n), O(9^n)$.

Can anyone give some idea on how to solve this kind of recursion questions.

I will assume the person stating the problem actually meant $\Theta$ where you write $O$; otherwise the question is trivial as Juho points out. Realising this may very well have been the point of the problem (or an intended shortcut for the observant), though.

Here is one basic idea to create an algorithm with runtime $\Theta(f(n))$: find a set of objects $S$ with $|S| = \Theta(f(n))$ and recursively enumerate it. If done correctly, this gives you a runtime in $\Omega(f(n))$; if you don't waste time, you get $\Theta(f(n))$.

Some hints for the concrete runtimes you want to achieve:

• Given a set $T$ of $n$ objects, $|T \times T| \in \Theta(n^2)$.

• Given a set $T$ of $n$ (distinguishable) objects, the set $\operatorname{Perm}(T)$ of all permutations of these objects has size $n!$.

• The set $\{0,1\}^n$ contains $2^n$ words.

Note that all these (simple) facts should be known from basic algorithm analysis and formal languages (and maybe combinatorics). The exam question can be solved by generalising and combining them.

StackExchange Computer Science Q#3297, answer score: 7