Complexity

Let's think above this intuitively, without using induction. We let $T(n)$ denote the running time of our algorithm for an input of size $n$ .

Clearly, our algorithm is recursive, as we see the procedure $fun$ contains two calls to itself on smaller inputs. Thus, the running time may be expressed in terms of the running time on smaller inputs. Thus we may express our running time as the recurrence $T(n)=T(n-1) + T(n-1) + O(1)=2T(n-1)+O(1)$ , where we use $O(1)$ since the amount of work required by each recursive call is constant (the amount of time needed to make the recursive call, and the mount of time required to combine the solution to the recursive call into the solution for the larger problem, since addition may be thought of as a constant operation on reasonably small integers).

Now, our algorithm will always reduce each subproblem into two smaller subproblems, each one less than the prior subproblem, until the boundary condition of the recurrence is reached (that is, when $n=1$ . So then let us ask, how many times may we subtract $1$ from $n$ until we get to $1$ ? The answer is $n-1$ times.

We can then think of our recurrence as $T(n)=2T(n-1)+O(1)=2(2(T(n-2))+O(1)+O(1)=\cdots=2^{n-1}T(1)+(n-1)\cdot O(1)$ .

Simplifying gives $T(n)=2^{n-1}T(1)+nO(1)-O(1)=O(2^{n-1})=O(2^{n})$ .

Let the runtime of computing fun(n) be $g(n)$ . It is obvious that $g(n) = 2g(n-1)$ because we need to run two fun(n-1) to achieve fun(n) . Simple induction lead us to $g(n) = 2^n g(1)$ . Since $g(1)$ takes constant time, the time complexity is $O(g(n)) = O(2^n g(1)) = O(2^n)$ .