Time and Space Complexities PDF

+-----------------+-----------------+-----------------+-----------------+ | Problem | Time complexity | Space | Base | | | | complexity | | +=================+=================+=================+=================+ | Jo...

+-----------------+-----------------+-----------------+-----------------+ | Problem | Time complexity | Space | Base | | | | complexity | | +=================+=================+=================+=================+ | Josephus | O(n) | | return | | | | | (josephus(n - | | | | | 1, k) + k - 1) | | | | | % n + 1 | | | | | | | | | | where n = | | | | | number of | | | | | people | | | | | | | | | | k = every kth | | | | | person is | | | | | eliminated | +-----------------+-----------------+-----------------+-----------------+ | Manachers | O(n) | O(n) | to find longest | | algorithm | | | palindromic | | | | | substring | +-----------------+-----------------+-----------------+-----------------+ | Maneuvering | O(n) | | calculate count | | algorithm | | | of paths in a | | | | | matrix from | | | | | bottom to top | +-----------------+-----------------+-----------------+-----------------+ | Maze solving | O(2\^(n\*n)) | O(n\*n) | 1\. create a | | | | | recursive | | | | | function to | | | | | explore the | | | | | matrix from | | | | | the current | | | | | position (i, | | | | | j), marking | | | | | valid paths | | | | | as 1, and | | | | | checking if | | | | | the | | | | | destination | | | | | is reached. | | | | | | | | | | 2. recursively | | | | | call for the | | | | | next positions | | | | | (i+1, j) and | | | | | (i, j+1), | | | | | unmarking | | | | | positions when | | | | | backtracking. | +-----------------+-----------------+-----------------+-----------------+ | Weighted | O(n\^n) | | | | substring | (QuadraticTime | | | | | Complexity) | | | +-----------------+-----------------+-----------------+-----------------+ | Sorted unique | O(P\*Q) | O(n) | | | permutation | | | | +-----------------+-----------------+-----------------+-----------------+ | Selection sort | O(n\*2) | O(1) | | | and quick sort | | | | +-----------------+-----------------+-----------------+-----------------+ | Move hyphen to | O(n) | O(1) | | | the beginning | | | | +-----------------+-----------------+-----------------+-----------------+ | Longest | O(n) | O(1) | | | sequence of 1s | | | | +-----------------+-----------------+-----------------+-----------------+ | Nibble swap | | | (x & 0x0F) \\> 4 | +-----------------+-----------------+-----------------+-----------------+ | Block swap | O(n) | O(1) | | +-----------------+-----------------+-----------------+-----------------+ | Max product | O(n) | O(1) | | | subarray | | | | +-----------------+-----------------+-----------------+-----------------+ | Max sum of | O(R\*C)  | O(1) | int sum = | | hourglass | | | (mat\[i\]\[j\] | | matrix | | | + mat\[i\]\[j + | | | | | 1\] + | | | | | | | | | | mat\[i\]\[j + | | | | | 2\]) + (mat\[i | | | | | + 1\]\[j + 1\]) | | | | | + | | | | | | | | | | (mat\[i + | | | | | 2\]\[j\] + | | | | | mat\[i + 2\]\[j | | | | | + 1\] + | | | | | | | | | | mat\[i + 2\]\[j | | | | | + 2\]); | | | | | | | | | | max\_sum = | | | | | Math.max(max\_s | | | | | um, | | | | | sum); | +-----------------+-----------------+-----------------+-----------------+ | Binary | O(log n) | | String s = | | palindrome | | | Integer.toBinar | | | | | yString(N); | | | | | | | | | | int i = 0, j = | | | | | s.length() - 1; | | | | | | | | | | while (i \< j) | | | | | { | | | | | | | | | | if (s.charAt(i) | | | | | != s.charAt(j)) | | | | | { | | | | | | | | | | return false; | | | | | | | | | | } | | | | | | | | | | i++; | | | | | | | | | | j\--; | | | | | | | | | | } | | | | | | | | | | return true; | +-----------------+-----------------+-----------------+-----------------+ | Euclid\'s | O(log(min(a, | | gcd | | algorithm | b))) | | | +-----------------+-----------------+-----------------+-----------------+ | Karatsuba | |  | a.c = 12 x 56 = | | | | | 672 | | | | | | | | | | Step 2: Compute | | | | | b.d = 34 x 78 = | | | | | 2652 | | | | | | | | | | Step 3: Compute | | | | | (a+b)(c+d) = 46 | | | | | x 134 = 6164 | | | | | | | | | | Step 4: Compute | | | | | (3)-(2)-(1)=616 | | | | | 4-2652-672 | | | | | = 2840 | +-----------------+-----------------+-----------------+-----------------+ | Leaders in an | O(n) | O(n) | int max = | | array | | | arr\[n - 1\]; | | | | | | | | | | ans.add(arr\[n- | | | | | 1\]); | | | | | | | | | | for (int i = n | | | | | - 2; i \>= 0; | | | | | i\--) | | | | | | | | | | if (arr\[i\] \> | | | | | max) { | | | | | | | | | | ans.add(arr\[i\ | | | | | ]); | | | | | | | | | | max = arr\[i\]; | +-----------------+-----------------+-----------------+-----------------+ | Majority | O(n\*n) | O(1) | Appears more | | element -- | | | than n/2 times | | trivial | | | | | solution | | | | +-----------------+-----------------+-----------------+-----------------+ | Majority | O(n\^n) in case | O(1) | | | element -- | of BST | | | | binary search | | | | | tree | O(nlogn) in | | | | | case of | | | | | balanced BT | | | +-----------------+-----------------+-----------------+-----------------+ | Majority | O(n) | O(1) | | | element | | | | | --linear | | | | | solution | | | | +-----------------+-----------------+-----------------+-----------------+ | Majority | O(n) | O(1) | | | element -- | | | | +-----------------+-----------------+-----------------+-----------------+ | Alice apple | | | - [If](https: | | | | | //www.geeksforg | | | | | eeks.org/python | | | | | -if-else/) | | | | | **M** is | | | | | less than | | | | | equal to | | | | | **S\*K** | | | | | then print | | | | | **M.** | | | | | | | | | | - [Else | | | | | if](https:/ | | | | | /www.geeksforge | | | | | eks.org/python- | | | | | if-else/) | | | | | **M** is | | | | | less than | | | | | equal to | | | | | **S\*K+E+W* | | | | | * | | | | | then print | | | | | **S\*K + | | | | | (M-S\*K)** | | | | | | | | | | - [Else](http | | | | | s://www.geeksfo | | | | | rgeeks.org/pyth | | | | | on-if-else/) | | | | | print | | | | | **-1.** | +-----------------+-----------------+-----------------+-----------------+