Skip to content

Commit 72408bf

Browse files
NeaByteLabNeaByteLab
committed
docs(time-complexity): document algorithm complexity notes 💡
- Annotate all algorithm implementations with complexity notes - Convert inline comments to structured JSDoc blocks - Add param and returns documentation to functions
1 parent 8cb04c9 commit 72408bf

8 files changed

Lines changed: 138 additions & 49 deletions

File tree

‎DEEP-NOTES/Time-Complexity/o-1-constant.md‎

Lines changed: 17 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -42,29 +42,37 @@ Not O(1): scanning the whole array to find something (that's at least O(n)), or
4242
**Good: constant-time access by index**
4343

4444
```typescript
45-
// NOTE: Single array index access - same cost whether arr has 10 or 10M elements.
46-
// O(1).
45+
/**
46+
* Get first array element.
47+
* @description Single index access regardless of array size.
48+
* @param arr - Source array to access
49+
* @returns First element or undefined
50+
*/
4751
function getFirst<T>(arr: T[]): T | undefined {
48-
return arr[0] // one access, regardless of arr.length
52+
return arr[0]
4953
}
5054
```
5155

5256
**Good: hash lookup (average case)**
5357

5458
```typescript
55-
// NOTE: Map.get() is O(1) average with good hash.
56-
// No scan over keys.
59+
/** User lookup by ID. */
5760
const userById = new Map<string, User>()
58-
const user = userById.get(id) // O(1) average
61+
const user = userById.get(id)
5962
```
6063

6164
**Bad:** getting first element by scanning (O(n), not O(1))
6265

6366
```typescript
64-
// NOTE: find() may scan up to n elements.
65-
// Linear, not constant.
67+
/**
68+
* Find element by scanning array.
69+
* @description Scans up to n elements - linear time.
70+
* @param arr - Source array to search
71+
* @param predicate - Matching function
72+
* @returns First matching element or undefined
73+
*/
6674
function getFirstByScan<T>(arr: T[], predicate: (x: T) => boolean): T | undefined {
67-
return arr.find(predicate) // touches up to n elements
75+
return arr.find(predicate)
6876
}
6977
```
7078

‎DEEP-NOTES/Time-Complexity/o-2-n-exponential.md‎

Lines changed: 20 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -42,17 +42,21 @@ You do **not** get O(2ⁿ) from a single loop (O(n)) or from nested loops with a
4242
**Good example: subset enumeration (2ⁿ subsets)**
4343

4444
```typescript
45-
// NOTE: Each element: include or exclude → 2 choices per element.
46-
// → 2ⁿ leaves in recursion tree.
45+
/**
46+
* Generate power set of array.
47+
* @description Each element has 2 choices, yielding 2ⁿ subsets.
48+
* @param arr - Source array for power set
49+
* @returns Array of all subsets
50+
*/
4751
function powerSet<T>(arr: T[]): T[][] {
4852
const result: T[][] = []
4953
function go(i: number, path: T[]) {
5054
if (i === arr.length) {
5155
result.push([...path])
5256
return
5357
}
54-
go(i + 1, path) // exclude
55-
go(i + 1, path.concat(arr[i])) // include
58+
go(i + 1, path)
59+
go(i + 1, path.concat(arr[i]))
5660
}
5761
go(0, [])
5862
return result
@@ -62,8 +66,12 @@ function powerSet<T>(arr: T[]): T[][] {
6266
**Good example: naive recursive Fibonacci (exponential calls)**
6367

6468
```typescript
65-
// NOTE: Two branches per call, depth n → call tree has ~2ⁿ nodes → O(2ⁿ).
66-
// Use DP or memo for O(n).
69+
/**
70+
* Calculate Fibonacci number.
71+
* @description Two branches per call creates ~2ⁿ nodes.
72+
* @param n - Fibonacci index to compute
73+
* @returns Fibonacci value at index n
74+
*/
6775
function fib(n: number): number {
6876
if (n <= 1) {
6977
return n
@@ -75,8 +83,12 @@ function fib(n: number): number {
7583
**Bad (not exponential):** one loop over n is O(n), not 2ⁿ.
7684

7785
```typescript
78-
// NOTE: Single pass over n elements → O(n).
79-
// Exponential needs "2 choices per step, n steps."
86+
/**
87+
* Sum all elements in array.
88+
* @description Single pass over n elements, linear time.
89+
* @param arr - Array of numbers to sum
90+
* @returns Total sum of all elements
91+
*/
8092
function sumArray(arr: number[]): number {
8193
let sum = 0
8294
for (const x of arr) {

‎DEEP-NOTES/Time-Complexity/o-log-n-logarithmic.md‎

Lines changed: 21 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -54,8 +54,13 @@ Example: for n = 1,000,000, log₂(n) ≈ 20. So about 20 comparisons instead of
5454
**Good: binary search (sorted array)**
5555

5656
```typescript
57-
// NOTE: Each step halves the range; at most ~log₂(n) iterations.
58-
// → O(log n).
57+
/**
58+
* Binary search on sorted array.
59+
* @description Halves range each step, at most log₂(n) iterations.
60+
* @param arr - Sorted array to search
61+
* @param target - Value to find
62+
* @returns Index of target or -1
63+
*/
5964
function binarySearch(arr: number[], target: number): number {
6065
let left = 0
6166
let right = arr.length - 1
@@ -77,8 +82,13 @@ function binarySearch(arr: number[], target: number): number {
7782
**Good: balanced BST lookup.** Same idea: each step goes left or right, so you follow one path of length O(log n).
7883

7984
```typescript
80-
// NOTE: One path from root to leaf; tree height O(log n) when balanced.
81-
// → O(log n).
85+
/**
86+
* Lookup key in balanced BST.
87+
* @description One path from root to leaf, height is O(log n).
88+
* @param node - Root node of BST
89+
* @param key - Key to search for
90+
* @returns Matching node or null
91+
*/
8292
function bstLookup(node: BSTNode | null, key: number): BSTNode | null {
8393
if (node === null || node.key === key) {
8494
return node
@@ -93,8 +103,13 @@ function bstLookup(node: BSTNode | null, key: number): BSTNode | null {
93103
**Bad:** linear search on a sorted array (O(n)). Same input as binary search, but we scan one by one instead of halving.
94104

95105
```typescript
96-
// NOTE: Scans every element until found - O(n).
97-
// Use binary search when sorted.
106+
/**
107+
* Linear search on sorted array.
108+
* @description Scans every element until found, O(n) time.
109+
* @param arr - Array to search (should be sorted)
110+
* @param target - Value to find
111+
* @returns Index of target or -1
112+
*/
98113
function linearSearchSorted(arr: number[], target: number): number {
99114
for (let i = 0; i < arr.length; i++) {
100115
if (arr[i] === target) {

‎DEEP-NOTES/Time-Complexity/o-n-cubic.md‎

Lines changed: 19 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -42,8 +42,13 @@ If you have three nested loops all ranging over _n_, you're in O(n³) territory
4242
**Good example: naive matrix multiply (two n×n matrices)**
4343

4444
```typescript
45-
// NOTE: Three nested loops over n → n³ multiplications/adds → O(n³).
46-
// Strassen does better.
45+
/**
46+
* Multiply two n×n matrices.
47+
* @description Three nested loops over n, n³ operations.
48+
* @param A - First matrix operand
49+
* @param B - Second matrix operand
50+
* @returns Result matrix product
51+
*/
4752
function matrixMultiply(A: number[][], B: number[][]): number[][] {
4853
const n = A.length
4954
const C: number[][] = Array(n)
@@ -63,8 +68,11 @@ function matrixMultiply(A: number[][], B: number[][]): number[][] {
6368
**Good example: Floyd–Warshall (all-pairs shortest paths).** Three nested loops over vertices, O(n³).
6469

6570
```typescript
66-
// NOTE: k, i, j each 0..n−1 → O(n³).
67-
// Standard for all-pairs shortest paths on dense graphs.
71+
/**
72+
* Floyd-Warshall all-pairs shortest paths.
73+
* @description k, i, j each iterate 0..n−1, O(n³).
74+
* @param dist - Distance matrix to update in place
75+
*/
6876
function floydWarshall(dist: number[][]): void {
6977
const n = dist.length
7078
for (let k = 0; k < n; k++) {
@@ -80,8 +88,13 @@ function floydWarshall(dist: number[][]): void {
8088
**Bad (not cubic):** two nested loops over n → O(n²), not O(n³).
8189

8290
```typescript
83-
// NOTE: Only two loops over n → O(n²).
84-
// Cubic needs three nested loops.
91+
/**
92+
* Compute pair-wise product sum.
93+
* @description Only two loops over n, O(n²) time.
94+
* @param A - First matrix operand
95+
* @param B - Second matrix operand
96+
* @returns Sum of element-wise products
97+
*/
8598
function pairsOnly(A: number[][], B: number[][]): number {
8699
const n = A.length
87100
let total = 0

‎DEEP-NOTES/Time-Complexity/o-n-factorial.md‎

Lines changed: 12 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -43,8 +43,12 @@ You do **not** get O(n!) from subset enumeration (that's O(2ⁿ)) or from a fixe
4343
**Good example: generate all permutations (n!)**
4444

4545
```typescript
46-
// NOTE: Builds every ordering of n elements → n! permutations → O(n!).
47-
// TSP brute-force uses this idea.
46+
/**
47+
* Generate all permutations of array.
48+
* @description Builds every ordering, n! permutations total.
49+
* @param arr - Source array to permute
50+
* @returns Array of all permutations
51+
*/
4852
function permutations<T>(arr: T[]): T[][] {
4953
const result: T[][] = []
5054
function go(rest: T[], path: T[]) {
@@ -67,8 +71,12 @@ function permutations<T>(arr: T[]): T[][] {
6771
**Bad (not factorial):** all subsets are 2ⁿ (each element in or out), not n! orderings.
6872

6973
```typescript
70-
// NOTE: Subsets = each element in or out → 2ⁿ, not n! orderings.
71-
// Factorial = every permutation.
74+
/**
75+
* Generate power set of array.
76+
* @description Each element in or out, 2ⁿ subsets.
77+
* @param arr - Source array for power set
78+
* @returns Array of all subsets
79+
*/
7280
function powerSet<T>(arr: T[]): T[][] {
7381
const result: T[][] = []
7482
function go(i: number, path: T[]) {

‎DEEP-NOTES/Time-Complexity/o-n-linear.md‎

Lines changed: 19 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -41,8 +41,12 @@ Nested loops over the same _n_ (e.g. for each i, for each j in the same array up
4141
**Good: single loop, constant work per element**
4242

4343
```typescript
44-
// NOTE: One pass over n elements, O(1) work per element.
45-
// → O(n).
44+
/**
45+
* Sum all array elements.
46+
* @description One pass over n elements, linear time.
47+
* @param arr - Array of numbers to sum
48+
* @returns Total sum of elements
49+
*/
4650
function sum(arr: number[]): number {
4751
let total = 0
4852
for (const x of arr) {
@@ -55,8 +59,13 @@ function sum(arr: number[]): number {
5559
**Good: find index (worst case)**
5660

5761
```typescript
58-
// NOTE: Worst case touches all n elements (target at end or missing).
59-
// Still one pass → O(n).
62+
/**
63+
* Find index of target value.
64+
* @description Worst case touches all n elements.
65+
* @param arr - Array to search
66+
* @param target - Value to find
67+
* @returns Index of target or -1
68+
*/
6069
function indexOf<T>(arr: T[], target: T): number {
6170
for (let i = 0; i < arr.length; i++) {
6271
if (arr[i] === target) {
@@ -70,8 +79,12 @@ function indexOf<T>(arr: T[], target: T): number {
7079
**Bad:** two nested loops over the same array (typically O(n²))
7180

7281
```typescript
73-
// NOTE: Nested loops over same n → n×(n−1)/2 comparisons.
74-
// O(n²), not O(n).
82+
/**
83+
* Check for duplicates using nested loops.
84+
* @description Nested loops yield n×(n−1)/2 comparisons.
85+
* @param arr - Array to check for duplicates
86+
* @returns True if duplicate exists
87+
*/
7588
function hasDuplicateQuadratic(arr: number[]): boolean {
7689
for (let i = 0; i < arr.length; i++) {
7790
for (let j = i + 1; j < arr.length; j++) {

‎DEEP-NOTES/Time-Complexity/o-n-log-n-linearithmic.md‎

Lines changed: 18 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -55,8 +55,13 @@ Same idea applies to heapsort and to the average case of quicksort (with a prope
5555
**Good: merge sort (merge step O(n), log n levels)**
5656

5757
```typescript
58-
// NOTE: merge() does one pass over left+right → O(n).
59-
// mergeSort has ~log n levels → O(n log n).
58+
/**
59+
* Merge two sorted arrays.
60+
* @description One pass over left plus right, O(n) work.
61+
* @param left - Left sorted array
62+
* @param right - Right sorted array
63+
* @returns Merged sorted array
64+
*/
6065
function merge(left: number[], right: number[]): number[] {
6166
const out: number[] = []
6267
let i = 0
@@ -71,8 +76,12 @@ function merge(left: number[], right: number[]): number[] {
7176
return out.concat(left.slice(i), right.slice(j))
7277
}
7378

74-
// NOTE: Split in half each time (log n levels).
75-
// Merge at each level is O(n).
79+
/**
80+
* Sort array using merge sort.
81+
* @description Split in half each time, log n levels.
82+
* @param arr - Array to sort
83+
* @returns Sorted array
84+
*/
7685
function mergeSort(arr: number[]): number[] {
7786
if (arr.length <= 1) {
7887
return arr
@@ -87,8 +96,11 @@ function mergeSort(arr: number[]): number[] {
8796
**Bad: bubble sort (O(n²))**
8897

8998
```typescript
90-
// NOTE: Nested loops over n; up to n²/2 swaps in worst case.
91-
// → O(n²).
99+
/**
100+
* Sort array using bubble sort.
101+
* @description Nested loops over n, up to n²/2 swaps.
102+
* @param arr - Array to sort in place
103+
*/
92104
function bubbleSort(arr: number[]): void {
93105
for (let i = 0; i < arr.length; i++) {
94106
for (let j = 0; j < arr.length - 1 - i; j++) {

‎DEEP-NOTES/Time-Complexity/o-n-squared-quadratic.md‎

Lines changed: 12 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -42,8 +42,12 @@ If you have two nested loops and both ranges depend on _n_, ask: is this really
4242
**Bad: naive duplicate check, O(n²)**
4343

4444
```typescript
45-
// NOTE: All pairs (i,j) with j > i → n(n−1)/2 comparisons.
46-
// → O(n²).
45+
/**
46+
* Check for duplicate values.
47+
* @description All pairs with j > i, n(n−1)/2 comparisons.
48+
* @param arr - Array to check for duplicates
49+
* @returns True if duplicate found
50+
*/
4751
function hasDuplicate(arr: number[]): boolean {
4852
for (let i = 0; i < arr.length; i++) {
4953
for (let j = i + 1; j < arr.length; j++) {
@@ -61,8 +65,12 @@ function hasDuplicate(arr: number[]): boolean {
6165
**Better: one pass with a Set (O(n))**
6266

6367
```typescript
64-
// NOTE: Single pass; Set.has/add are O(1) average.
65-
// → O(n) total.
68+
/**
69+
* Check for duplicates using Set.
70+
* @description Single pass with O(1) Set operations.
71+
* @param arr - Array to check for duplicates
72+
* @returns True if duplicate found
73+
*/
6674
function hasDuplicateLinear(arr: number[]): boolean {
6775
const seen = new Set<number>()
6876
for (const x of arr) {

0 commit comments

Comments
 (0)