Perhaps you already know this, in which case I'm sorry for being pedantic. There are portions of the academy that also care about constant factors. They would

Perhaps you already know this, in which case I'm sorry for being pedantic. 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