| First, the usual way of just writing O(1) or O(n) or O(n^2) is kind of an abuse of notation. Big-O is a mapping from a function, like O(n -> 1) or (n -> n) or (n -> n^2) or (x -> sin x) to a set of functions. Function don't care about renaming of arguments. (n -> 2 n) is the same function as (x -> 2 x). When you write O(k log n) what you really mean is O((k, n) -> k log n) And you can indeed take it apart: O((k, n) -> k) * O((k, n) -> log n) == O((k, n) -> n log n) (For some suitable definition of what multiplication of sets of functions means.) That's very different from functions with single arguments like in your example. (And, yes, your example works. It's just a different thing.) |