1
$\begingroup$

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); 
    } 
$\endgroup$
0
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thank you so much ! but I am trying to understand how you got to this :"Clearly this minimum value is at most log(n) " ? this is actually the part that I didn't understand from the beginning … if we do log on both sides we will get : log(n-m) < m , you said that m at maximum is log(n) .. but why you ignored the minus m in this equation ? $\endgroup$ – memeeol Oct 24 '19 at 14:33
  • $\begingroup$ This is because $2^{\log_2 n} = n > n-\log_2 n$. $\endgroup$ – Yuval Filmus Oct 24 '19 at 14:34
  • $\begingroup$ thank you ! just one last thing : after I found the number of iteration can I say that we have log(n) iteration where each one takes 2^i time so we sum all of the 2^i (geometric series) and I did this and got to theta(n) ? because I found this approach easier or this is wrong ? $\endgroup$ – memeeol Oct 24 '19 at 14:52
  • $\begingroup$ This gives you an upper bound. For a lower bound you need a lower bound on the number of iterations. $\endgroup$ – Yuval Filmus Oct 24 '19 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.