Consider the following recurrence relation for generating a sequence $\{a_n\},n3$ :

$a_n=a_{n-1}+a_{n-2}+a_{n-3}+1,$ where $a_0=a_1=a_2=1.$

We want to write some algorithms that input an non$-$negative integer $n$ and then output $a_n.$ For each of the following cases, give a pseudo$-$code and show its time complexity.

$($Bonus$2)*$ An algorithm of which the time complexity is logarithmic in $n,$ i$.$e$.,O(logn).$