# Running time of a function $P$ calling itself via $P(P(n/2))$

int P(int n)
{
if (n==1)
return 1;
else
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

• 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$.
– plop
Feb 1, 2021 at 16:50
• 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).
– D.W.
Feb 2, 2021 at 0:24
• 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!
– D.W.
Feb 2, 2021 at 0:25
• 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!
– D.W.
Feb 2, 2021 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)$$.