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.
*/