Correct complexity estimation

nullskill · nullskill · commit ee11b16a2573 · 2023-08-04T09:25:05.000+03:00
diff --git a/lib/src/medium/22.generate_parentheses/main.dart b/lib/src/medium/22.generate_parentheses/main.dart
@@ -1,4 +1,9 @@
-/// The time and space complexity of this code is `O(4^n / &radic;n)`
+/// The average time and space complexity of this code is `O(4^n / &radic;n)`.
+/// This is because we have `2^n` left bracket and `2^(n-1)` right bracket
+/// combinations. Here we get `2^n x 2^(n-1) = 4^n`.
+/// There are also `&radic;n` invalid combinations with right bracket 
+/// on the left position and left bracket on the right position.
+/// That's why we have to divide `4^n` by `&radic;n`.
 
 class Solution {
   List<String> generateParenthesis(int n) {

-Original file line number
+Diff line change
@@ @@ -1,4 +1,9 @@ @@
 -/// The time and space complexity of this code is `O(4^n / √n)`
 +/// The average time and space complexity of this code is `O(4^n / √n)`.
 +/// This is because we have `2^n` left bracket and `2^(n-1)` right bracket
 +/// combinations. Here we get `2^n x 2^(n-1) = 4^n`.
 +/// There are also `√n` invalid combinations with right bracket
 +/// on the left position and left bracket on the right position.
 +/// That's why we have to divide `4^n` by `√n`.
 class Solution {
   List<String> generateParenthesis(int n) {