Fibonacci term in logarithmic time

  1. Recursive approach( time complexity: exponential )
  2. Dynamic Programming approach( time complexity: linear time with linear space usage)
  3. Linear time and constant space solution, which keeps track of only previous two terms, unlike DP solution, thus making the space complexity constant.
Fig 1
Fig 2
Power(A,n)
Y = I
while(n > 0)
if (n is odd)
Y = MM(Y,A)
A = MM(A,A)
n = n/2
return Y

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store