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 &lt;= k) return 1; 

      int result = 0; 
      for (int i = k; i &gt; 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 &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$.