How to implement Fibonacci algorithm in two ways in C++?

Question

I mean I wan to implement Fibonacci algorithm in both divide and conquer(D&C) method and dynamic programming and finally extract time complexity of both methods and compare the complexities and choose one of them.please guide me.

Akhil Garg · Answer

NO problem . . Accept the answer if it solved your problems. . :)

Joe Wilson · Answer

Thank you for your answers,

Akhil Garg · Answer

http://www.sanfoundry.com/cpp-program-implement-floyd-warshall-algorithm/ http://www.c-program-example.com/2011/10/c-program-to-implement-floyds-algorithm.html

Joe Wilson · Answer

Thank you for your answer, by the way, I had a problem in implementing Floyd Algorithm which calculate the shortest path , please guide me.

Akhil Garg · Answer

I don't know much about calculating complexity but if we are going for a loop till n than that is o(n) .loop inside loop its o(n^2). A simple line is having O(1) like that we can calculate i learned it long back. if you got ur answer accept answer.

Joe Wilson · Answer

Thank you for your guidance, I am in your debt, by the way, could you please explain about how to extract the time complexity according to the source code of program for example current program(Fibonacci Algorithms) I mean I want to extract time complexities in both programs and then compare them. please guide me.

Akhil Garg · Answer

#include using namespace std ; int main () { int i = 1 ; int j = 0 ; int k = 0 ; int h = 1 ; int t = 0 ; int n ; cin >> n ; while ( n ) { if ( n % 2 ) { t = j * h ; j = i * h + j * k + t ; i = ik + t ; } t = h * h ; h = 2 * k * h + t ; k = k * k + t ; n = n / 2 ; } cout j ; return 0 ; }

Joe Wilson · Answer

Thank you for your guide but I had a problem in implementing the divide and conquer method , so please guide me to solve it.

Akhil Garg · Answer

You can try divide and conquer and recursive and compare both.

Akhil Garg · Answer

What issue you are facing ??? I think complexity is high for floyd algo??

Akhil Garg · Answer

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-3-divide-and-conquer-strassen-fibonacci-polynomial-multiplication/