Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Suppose I have an algorithm that reads lines in a file(linear) and for each line in the file, it sorts each word(nlogn). This algorithm is mnlogn, where m is the number of lines and n is the number of characters in a word.
Asymptotically, as the file gets longer the number of lines becomes small in comparison to the number of characters, so the running time of this algorithm is O(nlogn)? How do you determine big O like this where the inputs are different?
The asymptotic running time of your algorithm is $O(mn\log n)$, as you mention. If we don't know anything further about $m$ or $n$, there is no way to simplify this. If you know that $m = O(f(n))$, then the running time is also $O(f(n)n\log n)$. For example, if you know that $m = O(\sqrt{n})$, then the running time is also $O(n^{1.5}\log n)$. It will be $O(n\log n)$ only if $m = O(1)$, that is, $m$ is constant.
