Exponentiation (Fast?)

What’s the best-case, worst-case, and average-case runtime of pow? Assume n = power. Please remember to define n, and provide a tight upper bound.

algorithm pow
 Input: positive integer b, non-negative integer p
 Output: computing b^p (i.e. b raised to power of p)

 if p = 0
	 return 1
 else if p = 1
	 return b
 else if p is even
	 temp = pow(b, p / 2)
	 return temp * temp
 else
	 return b * b * pow(b, p-2)

Edge Case

If $p=0$ or $p=1$, the program will return within the first 4 lines. (It should also check if b = 0 or b=1 as that would make any further computation redundant.)

Best Case

$O(log_{2}(p))$ if p is a power of 2.

Average Case

Assume n = p.

At first glance, it seems the average case would produce an average runtime of $O(log_2(n))$, but this would only be the case if p is purely a power of 2, which has a right-skewed distribution with a probability of $0.25$ for $n \in [2,16]$ a probability of$0.0$$0.05$ for $n \in [2,128]$ and a probability of $0.0005$ for $n \in [2,32768]$. So, as n approaches infinity this increasingly becomes a rarity.

The nuance is that even though there is a 50% chance that n is even, it is not guaranteed to stay even after being divided by two. In fact, there is evidence in the code below that the limit of the average number of times that a positive, even integer can be divided by 2 and remain an integer approaches 2 as n approaches infinity. In other words…

If $P(n_i) = 2^{x_i}*3^{y_i}5^{z_i}\dots$ is the prime factorization of $n_i \in \{2, 4, \dots,n\}\subset \N_{even}$ then

$$ \lim\limits_{n \rarr \infty} \frac{2}{n}\sum \{x_i\} = 2 $$

public static void main(String[] args) {
		int n = 100;
		int sum = 0;
		int k = 2;

		for (int j = 0; j < 7; j++) {
			for (int i = k; i <= n; i += 2) {
				sum += count2(i);
			}
			System.out.println("On average, an even number in [2," + n + "] will be divided by 2 " + (float) sum / (n / 2) + " times.");
			k = n+2;
			n *= 10;
		}
	}

public static int count2( int n) {
		if (n == 0) {
			return 0;
		} else if (n % 2 == 0) {
			return 1 + count2(n/2);
		} else {
			return 0;
		}

/**OUTPUT:
On average, an even number in [2,100] will be divided by 2 1.94 times.
On average, an even number in [2,1000] will be divided by 2 1.988 times.
On average, an even number in [2,10000] will be divided by 2 1.999 times.
On average, an even number in [2,100000] will be divided by 2 1.99988 times.
On average, an even number in [2,1000000] will be divided by 2 1.999986 times.
On average, an even number in [2,10000000] will be divided by 2 1.9999985 times.
On average, an even number in [2,100000000] will be divided by 2 1.9999996 times.
*/