[ShroudedNight]

'Costly' doesn't seem to require that O(k) be non-constant:

http://www.gii.upv.es/tlsf/