4 ms·

I think that what the author calls "divide and conquer" is actually "recursion". Also the complexity of naive fibonacci is exactly the fibonacci sequence so O(

I think that what the author calls "divide and conquer" is actually "recursion". Also the complexity of naive fibonacci is exactly the fibonacci sequence so O(2^n) is correct but less precise than O(phi^n)

slver 5y ago
"Recursion" is part of the "how" of the "why" of "divide and conquer" :P
aliceryhl 5y ago
Recursion is not the same as divide and conquer. Divide and conquer is a category of algorithms that you would often implement with recursion, but you don't have to. For example, consider the bottom-up implementation of merge sort [1]. This implementation is not recursive, but merge sort uses divide and conquer regardless of whether or not you implement it top-down or bottom-up. On the other hand, the naive fibonacci implementation that runs in exponential type is recursive, but it does not use divide and conquer. [1]: https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implement...
neonological 5y ago
All recursion can be translated into a loop and a stack. In the tail recursive case you don’t even need a stack, a loop would suffice. That means all divide and conquer algorithms can be implemented without recursion.
limoce 5y ago
Seems you got down-voted. I guess you're doing competitive programming? People that are good at CP never call "recursion with memoization" as "divide and conquer". Yeah, they just call it recursion. "Divide and conquer" in CP world seems to be specific to those problems whose subproblems are not overlapping (therefore completely "divided"), e.g. merge sort, segment trees. Considering the classic problem "Tower of Hanoi", is it "divide and conquer"? No to CP people, and even Wikipedia [0] does not explicitly regard it as "divide and conquer". [0]: https://en.wikipedia.org/wiki/Tower_of_Hanoi https://en.wikipedia.org/wiki/Tower_of_Hanoi

slver 5y ago

"Recursion" is part of the "how" of the "why" of "divide and conquer" :P

aliceryhl 5y ago

Recursion is not the same as divide and conquer. Divide and conquer is a category of algorithms that you would often implement with recursion, but you don't have to. For example, consider the bottom-up implementation of merge sort [1]. This implementation is not recursive, but merge sort uses divide and conquer regardless of whether or not you implement it top-down or bottom-up. On the other hand, the naive fibonacci implementation that runs in exponential type is recursive, but it does not use divide and conquer. [1]: https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implement...

neonological 5y ago

All recursion can be translated into a loop and a stack. In the tail recursive case you don’t even need a stack, a loop would suffice. That means all divide and conquer algorithms can be implemented without recursion.

limoce 5y ago

Seems you got down-voted. I guess you're doing competitive programming? People that are good at CP never call "recursion with memoization" as "divide and conquer". Yeah, they just call it recursion. "Divide and conquer" in CP world seems to be specific to those problems whose subproblems are not overlapping (therefore completely "divided"), e.g. merge sort, segment trees. Considering the classic problem "Tower of Hanoi", is it "divide and conquer"? No to CP people, and even Wikipedia [0] does not explicitly regard it as "divide and conquer". [0]: https://en.wikipedia.org/wiki/Tower_of_Hanoi https://en.wikipedia.org/wiki/Tower_of_Hanoi