The big$-$O runtime for the recursive Fibonacci algorithm is O$(2$n$).$  To see why this is$,$ imagine drawing a tree where each node represents a call to the recursive algorithm. A node is a leaf node if it is a base case, otherwise it becomes the parent node for the two recursive calls made by that node. The result is a binary tree. This allows you to visualize how many recursive calls are made when calling the recursive Fibonacci algorithm. The amount of work involved in a single call is constant so now we just need to figure out how many calls are made $($ or how many nodes are in the tree$).$  If the binary tree were complete then the number of nodes would be $2$n$.$  The tree is not complete since the right side $($n$-2)$ is always smaller than the left node $($n$-1).$  This leads to an actual O$(1\mathrm{.}6180$n$)$ but for our purposes O$(2$n$)$ is good enough. What is the big$-$O runtime for the iterative Fibonacci algorithm?  

Answer rating: 100% (QA)

The iterative version of Fibonacci algorithm has On runnin... View the full answer