I'll probably get downvoted but I'm not a huge fan of Big-O notation(hence the k). It's very hand-wavey about the things that have a significant impact on performance(like cache misses).
Great from the ivory tower of academia but down in the real world we like things that run fast :).
There are portions of the academy that also care about constant factors. They would write what, I think, you mean by O(kN) as k * N.
If you need more precision, such as: "There's an order N term with constant factor k and some lower order terms whose constants I don't know (or don't care to calculate)", you could write that as: k * N + o(N). The little o means terms that grow strictly slower than N.
Edit: formatting
Edit2: I should have conceded that I'm not aware of anyone who attempts to use O-notation to talk about cache goodness. That certainly is swept under the covers of "Assume a perfect RAM machine" :P
I enjoy breaking out Radix because it's one of those thing's that's so unintuitive when you come at it from a traditional CS perspective. AFAIK the only book I'm aware of that approaches data structures with a consideration for this type of performance is Real-Time Collision Detection(which is basically datastructures for 3D spatial domains).