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); } `