The sequence $(f_{n})_{n \in \mathbb{N}}$ is defined by $f_{0} := 0, f_{1} := 1$ and $f_{n} := 3f_{n-1}-2f_{n-2}$ for $n \in \mathbb{N}_{0} \setminus \{0,1\}$.
Is there an algorithm that takes an $n \in \mathbb{N}_{0}$ and returns $f_{n}$ in $\theta(n^n)$ ?
The algorithm needs to be efficient (means there must not be any loops or calculations for artificially slow down the algorithm).
Two very short (just descriptive) examples for the calculation in $\theta(1)$ and $\theta(2^n)$:
$\theta(1)$: set the $n_{th}$ bit to 1 and subtract 1
$\theta(2^n)$: the recursive form $f_{n} := 3f_{n-1}-2f_{n-2}$