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

alexandru Permalink
July 07, 2009, 12:50

You can always use the O(logN) algorithm to compute nth fibonacci number (or O(NlogN) using your analysis). Your article's point is that big numbers (ie. not implemented in the hardware) don't have constant time operations. :|

Comment Responses

ramsandesh Permalink
April 22, 2010, 02:52

excuse me sir,
I m ram sandesh.I m doing my B.tech degree.I m interested in knowing this algorithm with time complexity of O(log n).can u please mail me back graph & algorithm.i guess u have done with matrix multiplication method...

William Permalink
May 26, 2011, 04:08

Actually, the «O(log n)» algorithm is not O(n log n) but O(n^a) where a single call is also O(n^a). If you use naïve long multiplication, a is 2; if you use Karatsuba multiplication, a is log(3)/log(2), which is better.

Reply To This Comment

(why do I need your e-mail?)

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

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

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