issues
search
mmore500
/
hstrat-algorithm-analysis
Formal analysis of the hereditary stratigraphy algorithm
0
stars
0
forks
source link
Prove stratum retention algorithm uncertainty bounds
#5
Open
mmore500
opened
1 year ago
mmore500
commented
1 year ago
[ ] fixed-resolution algorithm
O(1)
[ ] depth-proportional resolution algorithm
O(n)
[ ] recency-proportional resolution algorithm
O(m)
[ ] geometric sequence nth root algorithm
O(n * m)
[ ] curbed recency-proportional resolution algorithm
O(m)
-> (degrades to) ->
O(n * m)
this is probably trivial once recency-proportional and geometric sequence nth root algorithms are proved
where
m
is generations elapsed since MRCA
O(1)O(n)O(m)O(n * m)O(m)-> (degrades to) ->O(n * m)where
mis generations elapsed since MRCA