2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – FrankW
    Nov 5, 2014 at 6:47

1 Answer 1

1
$\begingroup$

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.

$\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.