# Big O notation and "input"

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?

• Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. Nov 5 '14 at 6:47

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.