MIT's Introduction to Algorithms, Lecture 3: Divide and Conquer

You're viewing a comment by Steve and its responses.

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
else
y = Recursive-Power(x, (n-1)/2)
return y*y*x

Reply to this comment

Reply To This Comment

(why do I need your e-mail?)

(Your twitter name, if you have one. (I'm @pkrumins, btw.))

Comment Help

Type first 3 letters of your name: (just to make sure you're a human)

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