# Time complexity dependent on magnitude of input [duplicate]

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?

• Time complexity on magnitude of input? Can you define it more? – Mr. Sigma. Dec 2 '18 at 23:52
• Yes, $O(nm)$, assuming the time complexity of the operations represented by "..." on the last line of the code is $O(1)$ – John L. Dec 3 '18 at 4:45
• Depends on $L$ and what's in the loop, obviously! (And what range means.) – Raphael Dec 3 '18 at 16:56
• 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. – Raphael Dec 3 '18 at 16:57
• Relevant for identifying the worst case: is L a list or set? – 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$$.
• Using $n$ with another meaning as in the algorithm is a bad idea. – Raphael Dec 3 '18 at 16:59
• 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$! – Raphael Dec 3 '18 at 17:01