Fix complexity inconsistencies, enforce overhead, add missing variants

Fix complexity inconsistencies, enforce overhead, add missing variants #419