Is O(kn) linear complexity or quadratic complexity? Or does it depend on the k?
algorithm, complexity-theory, time-complexity
Solution
If `k` is a constant, then any O(kn) function is O(n), i.e. linear
If `k` is a function of `n` and is O(n), then any O(kn) function is O(n^2). n/2 is O(n). Furthermore, `(n^2)/2` is not O(n), and so if `k` is close to `n/2` then `kn` is not O(n).
If `k` is not O(n), then `kn` is not O(n^2).
Problem
If n is very big, and k is very small, can I say that O(kn) is linear complexity? What if k is closed to n/2, but not more than n/2? Do I consider it still as linear complexity? Or quadratic complexity O(n^2)? Is there a limit to how big k is, to consider O(kn) as quadratic complexity?