File tree Expand file tree Collapse file tree 1 file changed +3
-7
lines changed
Competitive Coding/Math/Catalan_Numbers Expand file tree Collapse file tree 1 file changed +3
-7
lines changed Original file line number Diff line number Diff line change @@ -5,16 +5,12 @@ They're similar to Fibonacci (very slightly)
5
5
The 2 different implementations vary only in terms of time taken!<br >
6
6
Basically we can implement in 3 different ways!<br >
7
7
8
- (1) Recursively <br >
9
- (2) Dynamic Programming <br >
10
- (3) Binomial Coefficient <br ><br >
8
+ * Recursively - Exponential time complexity <br >
9
+ * Dynamic Programming - O(n^2) <br >
10
+ * Binomial Coefficient - O(n) <br ><br >
11
11
12
12
Each of the above 3 implementations have a descending order of time complexities from (1) to (3) <br ><br >
13
13
14
- For (1) the time complexity is exponential<br >
15
- For (2) the time complexity is O(n^2)<br >
16
- For (3) the time complexity is O(n)<br ><br >
17
-
18
14
The Binomial implementation has the best time complexity while the Recursive implementation has the worst time complexity<br >
19
15
In this folder we have the Binomial and Recursive implementations of Catalan Numbers.<br ><br >
20
16
You can’t perform that action at this time.
0 commit comments