1
$\begingroup$

I want to express the asymptotic time complexity for the worst case scenario of sorting a list of $n$ strings, each string of length $k$ letters. Using merge-sort, sorting a list of $n$ elements requires $O(n\log n)$. Comparing two strings of length $k$ has a cost of $O(k)$. Therefore, the cost would be $O(kn\log n)$.

However, I know some restrictions about $k$ and $n$ due to the nature of the problem. In particular, I know that for any list, $0 \lt k \leq 20$, and $0 \lt n \leq 80000$. In other words, the number of words in a list might vary in a much larger range than the length of the words.

In that case, would it be correct to say that $n$ dominates over $k$ and therefore the cost could be expressed as $O(n\log n)$? Or does the fact that we are discussing asymptotic costs make those restriction meaningless (as we are describing how the algorithm is impacted by the growth of each variable, regardless of how much they can actually grow)? In general, if two variables are independent, is it possible to dismiss one of them from the asymptotic cost under certain circumstances?

$\endgroup$
  • $\begingroup$ If you have upper bounds on $k$ and $n$, the complexity is simply $O(1)$. $\endgroup$ – Yuval Filmus May 3 at 15:20
  • $\begingroup$ If you know (say) that $k = \log n$, then $O(kn\log n) = O(n\log^2 n)$. Note that you cannot "dismiss" $k$. You could dismiss $k$ if you were adding it: $O(k + \log n) = O(\log n)$. $\endgroup$ – Yuval Filmus May 3 at 15:22
  • $\begingroup$ @YuvalFilmus I believe these comments merit its own answer :) In particular, when you say that in the case of addition I could dismiss k, you still mean in the case that k = log(n), not in the general case, right? $\endgroup$ – user2891462 May 3 at 15:48
  • $\begingroup$ Right, I mean in that particular case. $\endgroup$ – Yuval Filmus May 3 at 15:49
1
$\begingroup$

First of all, if $k$ and $n$ are bounded then all complexities trivialize to $O(1)$. Hence a better assumption is something like $k = O(\log n)$. Under this assumption, you can, for example, say that $O(k + n) = O(n)$, and even $O(k + \log n) = O(\log n)$. However, you cannot say that $O(kn) = O(n)$, since it's not necessarily true! If $k = \log n$, then it's not true that $O(kn) = O(n)$. Instead, all you can say is that $O(kn) = O(n\log n)$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.