Are they the same or not? How do you tell if something is a top-down algorithm or a divide-and-conquer algorithm? I was taught that writing an algorithm for F_{n} = F_{n-1} + F_{n-2} is a top-down algorithm. Why is it not a divide-and-conquer algorithm? Or is it both?
1 Answer
Divide-and-conquer would typically refer to partitioning a set of items and processing each part independently; merge sort is a good example.
The standard definition of nth Fibonacci number doesn't divide anything, and more importantly, the two parts aren't independent. Computing F_{n-2} is a crucial component of computing F_{n-1}.
