Time complexity of recursive function
Let $k_i = 2^i$, and define $m$ to be the minimum value such that $n-(m-1) \leq k_m$. It's not hard to check that the running time of $f_2$ is $\Theta(k_1 + \cdots + k_{m-1})$. Since $k_i$ grows exponentially, $k_1 + \cdots + k_{m-1} = \Theta(k_m)$, and so the running time of $f_2$ is $\Theta(k_m)$.

It remains to find the minimum integer value of $m$ which satisfies $n-m &lt; k_m = 2^m$. Clearly this minimum value is at most $\log_2 n$, implying that $2^m \leq n$. This also means that the critical value of $m$ satisfies $2^m &gt; n-\log_2 n = \Omega(n)$. Therefore $k_m = \Theta(n)$, and so the running time of $f_2$ is $\Theta(n)$.

Regarding the space complexity, it is proportional to the depth of the recursion, which as we have seen is very close to $\log_2 n$.