int P(int n)
  if (n==1)
    return 1;
    return P(P(n/2));

How will this function P(P(n/2)) be executed and what will be the recurrence relation for this code?

Original image with the code

  • $\begingroup$ Work out the case of an input for the form $2^k$. Then, for a general $n$ bound it between $2^{k-1}<n\leq 2^k$. Note that for an input that it is a power of $2$, the input in the recursive call is $n/2$, which will also be a power of $2$, but with the exponent decreased by $1$. $\endgroup$ – plop Feb 1 at 16:50
  • 1
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX). $\endgroup$ – D.W. Feb 2 at 0:24
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – D.W. Feb 2 at 0:25
  • 1
    $\begingroup$ I find it hard to understand what you are asking. I'm not sure what "How will it be executed?" means or what kind of answer you are hoping for. Also, please ask only one question per post. Thank you! $\endgroup$ – D.W. Feb 2 at 0:25

There is an unwritten assumption that the input is always at least $1$ (otherwise your function never terminates). Under this assumption, it is easy to prove by induction that the function does terminate, and always returns $1$. Therefore in the expression $P(P(n/2))$, we are first invoking $P$ with the input $n/2$, and then with the input $1$. It follows that the running time $T(n)$ of your function satisfies the recurrence $$ T(n) = T(\lfloor n/2 \rfloor) + \Theta(1), $$ with initial condition $T(1) = \Theta(1)$. The solution is $T(n) = \Theta(\log n)$.


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.