Question

Which of the following implementations of Catalan numbers has the largest space complexity(Don’t consider the stack space)?

(a) Dynamic programming

(b) Binomial coefficients

(c) Recursion

(d) All have equal space complexities

This question was posed to me in an international level competition.

My question comes from Catalan Number using Dynamic Programming in division Dynamic Programming of Data Structures & Algorithms II

Answer 1

The correct option is (a) Dynamic programming

The best I can explain: The space complexities are as follows:

Dynamic programming: O(n)

Recursion: O(1)

Binomial coefficients: O(1).