complexity_analysis.md

Complexity Analysis

Time Complexity / Space Complexity (if it matters)

Day 1

Part 1: O(n)

Part 2: O(n)

where n is number of numbers

Day 2

Part 1: O(n)

Part 2: O(n)

where n is number of commands

Day 3

Part 1: O(LB)

Part 2: O(LB)

where L is number of lines, B is numbers of bits (string length)

Day 4

Part 1 & 2: O(NBS²)

where N is length of Bingo Numbers, B is number of Bingo Tables, S is width of Bingo Table

Day 5

Part 1: O(LS²) / O(S²)

Part 2: O(LS²) / O(S²)

where L is number of lines, S is width of the grid

Day 6 - Starting to get a bit hard

Part 1 (Brute Force): O(I*2^D)

Part 2 (Dynamic Programming): O(D + I)

where I is initial number of fishes, D is number of days

Day 7

Part 1: O(NlogN)

Part 2: O(NM)

where N is number of crabs, M is maximum of horizontal position of crabs

Day 9

Part 1: O(NM)

Part 2 (Flood Fill): O(NM)

where N is rows, M is cols

Day 15 - Dynamic Programming 2D

Part 1: O(N²) Does not work for all cases

Similar to DP 2D + Bellman-Ford

Part 2: O(K³N³)

where N is width and height of cave, K is number of times the cave width