# Te 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);      }