Recursion

By induction, clearly $func(n) = n$ for all $n$ . (The base case is $n \le 0$ ; the inductive case uses the inductive hypothesis twice to get $func(func(n-1)) = func(n-1) = n-1$ .)

Let $T(n)$ be the running time of the function with argument $n$ . We obtain the recurrence $T(n) = 2T(n-1) + O(1)$ , since $func(func(n-1))$ evaluates to $func(n-1)$ in $T(n-1)$ time, and to $n-1$ in further $T(n-1)$ time, before adding a constant time for the addition. Thus we can use induction again to see that $T(n) = \boxed{O(2^n)}$ .