In reading the paper "a strip-packing algorithm with absolute performance bound 2", the author gives a recursion formula $T(l)=T(l')+T(l'')+O(min\{l'\log{l'},l''\log{l'}',l\})$, where $l'+l''=l$,$l'>0$,$l''>0$, I'm confused about the complexity of the recurison formula, how to obtain $T(n)=O(n\log^2(n)/\log\log n)$?
https://epubs.siam.org/doi/10.1137/S0097539793255801
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Are $l$, $l'$, $n$ integers? $\endgroup$– John L.Jul 25, 2022 at 16:40
-
$\begingroup$ yes, all symbols are integers. $\endgroup$– Twilight7Aug 6, 2022 at 6:00
Add a comment
|