Time complexity analysis of power function

Question

This is the code which I'm finding time complexity using Extended master theorem.

int power(int a, int b)
{
    if(!b) return 1;
    int temp = power(a, b/2) * power(a, b/2);
    if(b%2==1) temp = temp *a;
    return a;
}

Now I think this is the correct recurrence relation => $T(n) = 2 T(n/2) + c$ It will be $\Theta (n^{log_22}) = \Theta(n) $ Right? First case of extended master theorem. Reference: https://www.geeksforgeeks.org/advanced-master-theorem-for-divide-and-conquer-recurrences/

int power(int a, int b)
{
    if(!b) return 1;
    int temp = power(a, b/2);
    temp * = temp;
    if(b%2==1) temp = temp *a;
    return a;
}

Now what will be the time complexity here $\Theta(n^0) = 1 ?$

Please share your thoughts

Answer 1

You are correct on the first one, I have nothing to add there.

On the second you have a basic recurrence T(n) = T(n/2) + c. (The T(n/2) comes from your recursive call to power(a, b/2) which only terminates once b reaches zero). This yields O(log n).

Makes sense?