You're replying to a comment by Steve.

August 22, 2008, 01:31

Nice summary. Your pseudo-code for the recursive power algorithm is not quite right. As written, it is still O(n). You don't get the benefit if you make each recursive call twice. For the O(log n) version, try:

Recursive-Power(x, n):
if n == 1
return x
if n is even
y = Recursive-Power(x, n/2)
return y*y
y = Recursive-Power(x, (n-1)/2)
return y*y*x

Reply To This Comment

(why do I need your e-mail?)

(Your twitter handle, if you have one.)

Type the word "cloud_85": (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.