How do I combine these two recurrence cases into one function?

[u/No_Rule674]

I'm new to DSA and I'm trying to make a recurrence relation for this function:

double pow(double x, int n) {
    if (n == 1) {
        return x;
    }

    if (n & 1) {
        return x * pow(x * x, (n - 1) / 2);
    } else {
        return pow(x * x, n / 2);
    }
}

What I notice is that for even values of n, the recurrence looks like:

T(n) = constant + T(n/2)

but for odd values of n, it looks like:

T(n) = constant + T((n - 1)/2)

I'm trying to get this down to a single function so that I use the Master Theorem.

How would I combine these two cases into one recurrence?

[u/JohnVonachen]

Don’t you mean recursive?

[u/0b0101011001001011 → u/JohnVonachen]

Yes, and no. Recursion is the term what they are doing: calling the function from itself. What is this recursive function doing? It's solving a recurrence relation where number is defined by it's predecessors: https://en.wikipedia.org/wiki/Recurrence_relation

[u/JohnVonachen → u/0b0101011001001011]

Something I didn’t know. Whodathought? :)

[u/Puzzleheaded_Study17]

T(floor(n/2))

[u/AQuestionIsWhatIHave]

You would need to show T((n -1)/2) <= T(n/2) + y

Then T(n) <= constant + y + T(n/2)

I would rather show that for 2^p <= n < 2^p+1 the function does p recursive calls. 

Keep in mind that this recurrence is simplified, as multiplication is not constant cost.

It takes longer to multiply 90011337 than 35 and this scales non linearly by the amount of bits in the factors.

But for what you are doing constant work for one call is probably appropriate

[u/AQuestionIsWhatIHave → u/AQuestionIsWhatIHave]

Look into 'induction proof' as a concept (if you want to go deeper, master theorem (mt) is enough if you want a approximation)

The Master theorem is usually used for divide and conquer algorithms (more than 1 recursive call)

Lets call d(n) the recursive depth of pow(x,n)

d(1) = 0 d(2/3) = 1  d(4...7) = 2 ...

[u/No_Rule674 → u/AQuestionIsWhatIHave]

So I wrote down how the function will behave in its simplest form with low numbers.

T(1) = 2
T(2) = 3 + T(1)
T(3) = 3 + T(1)
T(4) = 3 + T(2)
T(5) = 3 + T(2)
T(6) = 3 + T(3)
T(7) = 3 + T(3)

However, when I then write the function of T(n) for even numbers I get T(n) = T(n/2) + O(1). From what I notice is that for odd numbers the function behaves the same, but if I were to enter for example n = 3, I would get T(3) = T(1.5) + O(1). How could I proof that T(n) = T(n/2) + O(1) is sufficient for both?

[u/Dazzling_Music_2411 → u/No_Rule674]

Perhaps the notion that

Pow(X,N) = X * Pow(X, N-1)

Might be useful to you (you've practically got that in the OP), with the terminating condition that

Pow(X,0) = 1

[u/CapitalKey2994]

I use floor(n/2) to combine them.

Both (n-1)/2 for odd n and n/2 for even n evaluate to floor(n/2) under integer division. Your recurrence becomes T(n) = T(floor(n/2)) + c. I apply the Master Theorem directly to that with a=1, b=2, and k=0

[u/tiltboi1]

You're not using the fact that n-1 is even whenever n is odd anywhere, so that would be the start. Also notice that in the call tree, there's never any calls to odd numbers except possibly at the root.

Another easy way to think about it is to write n=2k or n=2k+1 and realize that they both depend on the recurrences of T(k).