Give an O(n) algorithm for computing a^n, given a and n. Give an
O(logn) algorithm for computing a^n, given that n is a power of 2.

Hi math01-ga,

Here are the algorithms you requested:

Give an O(n) algorithm for computing a^n, given a and n. 

int i = 0;
int total = 1;

while(i <= n)
{
	total = total*a;
}

return total;


Give an O(logn) algorithm for computing a^n, given that n is a power of 2.

int i = 1;
int total = a;

if(n == 0)
{
	return 1;
}
else
{
	while(i <= n)
	{
		total = total*total;
		i = i + i;
	}

	return total;
}

Please let me know if you have any questions :)

Cheers!

answerguru-ga

The o(n) algorithm has a bug, I think.  The loop control variable does
not change and therefore the loop will go forever.

That's correct jasontiger...the fixed algorithm should look like this:

int i = 0; 
int total = 1; 
 
while(i <= n) 
{ 
 total = total*a; 
 i++;
} 
 
return total;