I'm trying to analyze an algorithm that looks like this:

def foo(L):
    for n in L:
        for x in range(n):

What would be its time complexity? First I thought $O(n)$, where $n$ is the number of elements in $L$, but that seems a little optimistic given that numbers can become very large. Then I thought $O(n^2)$ but that seem quite arbitrary too. $O(nm)$ where $m$ is the maximum value in $L$ perhaps?

  • $\begingroup$ Time complexity on magnitude of input? Can you define it more? $\endgroup$ – Mr. Sigma. Dec 2 '18 at 23:52
  • $\begingroup$ Yes, $O(nm)$, assuming the time complexity of the operations represented by "..." on the last line of the code is $O(1)$ $\endgroup$ – John L. Dec 3 '18 at 4:45
  • $\begingroup$ Depends on $L$ and what's in the loop, obviously! (And what range means.) $\endgroup$ – Raphael Dec 3 '18 at 16:56
  • $\begingroup$ I think our reference question is enough to answer your question, or at least to guide you towards asking a more informed question (right now, you're attempting to pattern-match, not analyzing). (The second answer is probably more helpful here.) You can also check out questions tagged runtime-analysis+loops. $\endgroup$ – Raphael Dec 3 '18 at 16:57
  • $\begingroup$ Relevant for identifying the worst case: is L a list or set? $\endgroup$ – Raphael Dec 3 '18 at 17:01

Your result of seems correct, assuming none of the omitted operations modify the values of the variables n, L or x.

For a fixed value $k$ of n, the inner loop (for x in range(n):) loops over the set (or list; it is irrelevant for the analysis) $\{ 0, \dots, k - 1\}$, which contains $k$ elements. The outer loop (for n in L:) simply loops over each element of $L$ for a total of $|L|$ iterations, $|L|$ being the length of $L$. Thus, assuming the omitted operations are executed in $O(1)$ time, we obtain a time complexity of $O(m|L|)$ (as you propounded), where $m$ is the maximum value in $L$.

Incidentally, if you know the average value for the elements of $L$ you could also use the above reasoning to derive the average time complexity as well. (Just plug in the average value for $k$.)

As pointed out by @Raphael in the comments, of course, there is plenty of room for improvements if more assumptions are made about the contents of $L$.

| cite | improve this answer | |
  • $\begingroup$ Using $n$ with another meaning as in the algorithm is a bad idea. $\endgroup$ – Raphael Dec 3 '18 at 16:59
  • $\begingroup$ That's a very rough upper bound on the number of iterations of the inner loop. In fact, it may be off by a factor of $n$! $\endgroup$ – Raphael Dec 3 '18 at 17:01

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