Cost of resizing

Copyright Dr. Marek A. Suchenek 2011 - 2020

Cost of additive upsizing - calculations

k = ⌈((n-10)/5)⌉;
(∑_(i=0)^(k-1))(5 × i + 10)

Simplify[%]

(R^u)(n) = (5/2) (-2+Ceiling[(n/5)]) (1+Ceiling[(n/5)]) ≤ (5/2) (-2+((n+4)/5)) (1+((n+4)/5))

(5/2) (-2+Ceiling[(n/5)]) (1+Ceiling[(n/5)])≤(5/2) (-2+((4+n)/5)) (1+((4+n)/5))

N[(5/2) (-2+((n+4)/5)) (1+((n+4)/5))]

Simplify[%]

Expand[(1/10) (-6+n) (9+n)]

Limit[((-(27/5)+((3 n)/10)+((n^2)/10))/(n^2)), n -> ∞]

Average cost of upsizing per inserted element under assumption that no downsizing is ever made

(((R^u)(n) )/n)≤ (((1/10) (-6+n) (9+n))/n)

(((1/10) (-6+n) (9+n))/n)

Expand[(((-6+n) (9+n))/(10 n))]

Limit[(((3/10)-(27/(5 n))+(n/10))/n), n -> ∞]

Cost of multiplicative upsizing - calculations


(R^u)(n) = (∑_(i=0)^(k-1))(2^i)× 10

k = ⌈Log2[(n/10)]⌉;
(∑_(i=0)^(k-1))(2^i)× 10

(R^u)(n) =10 (-1+(2^(⌈(Subscript[log, 2])[(n/10)]⌉)))

Since  (n/10) ≤  (2^(⌈(Subscript[log, 2])[(n/10)]⌉)) < 2(n/10)

10 (-1+(n/10)) ≤   (R^u)(n) < 10 (-1+2(n/10))

n - 10 ≤   (R^u)(n) < 2n - 10

Average cost of upsizing per inserted element under assumption that no downsizing is eved made

1 - (10/n) ≤ (((R^u)(n) )/n)< 2 - (10/n)

Limit[1 - (10/n), n -> ∞]

Limit[2 - (10/n), n -> ∞]