So long as f,g: N→M and we have a reasonable definition of the magnitude ‖·‖:M→ℝ, it shouldn't matter what N is, since we can just define

O(f(n)) = O(g(n))

if and only if

sup_n∈N ‖f(n)‖/‖g(n)‖ < ∞.