O(d
n
) ∀ d > 1