I want to find the upper bound time complexity of this function.
I know how this is done using the induction method, but I can't find clear steps on how to solve it using the iteration method.
$T(n) = 3T(n-1) + \mathcal{O}(1)$ for $n>1$; otherwise $T(n) = \mathcal{O}(1)$
I am not sure how you would define the iterative method. A short search on the internet suggested that one should simple write out the first few terms and see if a pattern emerges. First note that being $O(1)$ is just being bounded by some $k$. $$ \begin{align} T(1)&\leq k\\ T(2)&\leq 3k+k\\ T(3)&\leq 3(3k+k)+k=3^2k+3k+k\\ T(4)&\leq 3(3^2k+3k+k)+k=3^3k+3^2k+3^1k+3^0k \end{align} $$ So it appears we have the pattern $$ T(n)\leq(3^{n-1}+...+3+1)k $$ and by the obviously correct statement $$ (x^{n-1}+...+x+1)(x-1)=x^n-1\\ \iff\\ x^{n-1}+...+x+1=\frac{x^n-1}{x-1} $$ we see that this is equivalent to $$ T(n)\leq\frac{3^n-1}{3-1}\cdot k $$ so that $T(n)=O(3^n)$.