In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively-defined objects. They are named after the Belgian mathematician Eugène Charles Catalan (1814–1894).
The first Catalan numbers for n = 0, 1, 2, 3, … are
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, … (sequence A000108 in the OEIS).
Recursive Approach:
package dp;
public class CatalanNumbers {
public static void main(String[] args) {
int n = 10;
long startTime = System.nanoTime();
System.out.println(FindCatalanNumber(n));
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println("Total Time (nanoseconds) : " + (totalTime));
}
private static int FindCatalanNumber(int n) {
if(n==0)
return 1;
int sum = 0;
for(int i=1;i<=n;i++)
sum += FindCatalanNumber(i-1) * FindCatalanNumber(n-i);
return sum;
}
}
output:
16796
Total Time (nanoseconds) : 758183
The time complexity of the above solution is O(4^n).
Can we do it more efficiently?
Yes, By using Dynamic programming.
package dp;
public class CatalanNumbers {
public static void main(String[] args) {
int n = 10;
long startTime = System.nanoTime();
System.out.println(FindCatalanNumber(n));
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println("Total Time (nanoseconds) : " + (totalTime));
}
static int[] dp = new int[15]; //currently expecting only 15 result items.
//increase the size if more is required.
private static int FindCatalanNumber(int n) {
if(n==0) {
dp[0] = 1;
return dp[0];
}
if(dp[n] != 0)
return dp[n];
int sum = 0;
for(int i=1;i<=n;i++)
sum += FindCatalanNumber(i-1) * FindCatalanNumber(n-i);
dp[n] = sum;
return dp[n];
}
}
16796
Total Time (nanoseconds) : 267705
The time complexity of this implementation is O(n^2) because to compute CatalanNumber(n), we need to compute all of the CatalanNumber(i) values between ) and n-1, and each one will be computed exactly once, in linear time.
