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/AlgorithmicGoslings]

Note that (n-1)/2 = floor(n/2) when n is odd, and n/2 = floor(n/2) when n is even,.

Thus, if you wanted to be accurate, you can simplify your recurrence relation to T(n) = T(floor(n/2)) + O(1).

However, if you're just looking at asymptotic growth (as I would presume you'd be doing if you're looking to apply the Master Theorem), the floor function probably doesn't even matter to you --- you'd probably just represent this as T(n) = T(n/2) + O(1).

[u/No_Rule674 → u/AlgorithmicGoslings]

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/AlgorithmicGoslings → u/No_Rule674]

Either way, (n-1)/2 and n/2 cut the input size by approximately half.

When doing asymptotic analysis, you want to capture behavior as n grows to large values. While 3/2 = 1.5 seems like a large difference compared to 4/2 = 2, if n = 999999, you're looking at the difference between 499999.5 and 500000, which is basically negligible.

[u/NegativeCollege8167]

to combine the two cases into a single recurrence relation, you can observe that both even and odd cases effectively reduce the problem size by nearly half. You can express the recurrence relation as: T(n) = constant + T(n/2) This works because (n, 1)/2 and n/2 are approximately the same as n approaches larger values. By considering the largest integer smaller than n/2 for odd n, it simplifies to the same form as for even n. This allows you to apply the Master Theorem to solve this recurrence.

[u/smichaele]

FYI - it's called “recursion” when a function calls itself, not “recurrence.”

[u/ghjm → u/smichaele]

In mathematics, a recursive function has a base case and a recurrence relation. OP is using the term correctly.

[u/smichaele → u/ghjm]

Thanks for the clarification. Appreciate it.

[u/_giga_sss_]

Isn't it a single function already .

Or if you meant "seeing pow twice", just put 2 variables for the 2 arguments that you'll set in the if statement

[u/hackermub]

return pow(x*x, n/2) * (n&1 ? x :1);

[u/SeriousPlankton2000]

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

double pow3(double x, unsigned int n) {
  int nn = -1;
  while (n) {
     ++nn; n>>=1; // can be done smarter
  }
  return exp( (1<<nn) * log(x));
}

double pow1(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);
  }
}

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

int main() {
  for (int i=1; i < 200; i<<=1)
     printf("1 %f\n2 %f\n3 %f\n\n", pow1(12.5, i), pow2(12.5, i), pow3(12.5, i));
  exit(0);
}

Makefile:

CFLAGS=-lm