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); 
    }
Improve this question
$\endgroup$

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
4
  • $\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$ Commented Oct 24, 2019 at 14:33
  • $\begingroup$ This is because $2^{\log_2 n} = n > n-\log_2 n$. $\endgroup$ Commented Oct 24, 2019 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$ Commented Oct 24, 2019 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$ Commented Oct 24, 2019 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.