# Time complexity of recursive function

I am trying to find out how they calculated the time complexity of this small function . I am studying for an exam and found this question and the final answer is given, but I am trying to understand how they got to this answer, I tried solving this problem using Iterative but when I tried to find the number of Iterations of this function I got stuck !

What I tried: let $$T(n,k)$$ represent the time complexity of $$g$$. It satisfies the recurrence

$$T(n,k)=ck+\sum_{j=1}^i(2^j-1)k + T(n-i,2^ik)$$

when $$i$$ is the number of iteration in this function, so according to this function the iteration ends when $$n\le k$$, which means $$n-i=2^ik$$, but I couldn't extract $$i$$ from the equation.

Here is the function, whose time and space complexity are stated to be $$\Theta(n)$$ and $$\Theta(\log n)$$:

   int g(int n, int k) {
if (n <= k) return 1;

int result = 0;
for (int i = k; i > 0; --i, ++result);

return result + g(n - 1, 2 * k);
}

int f2(int n) {
return g(n, 2);
}


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 < 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 > 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$$.
• This is because $2^{\log_2 n} = n > n-\log_2 n$. – Yuval Filmus Oct 24 '19 at 14:34