My understanding is the following:

Time = With the initial not state is just to check if there are no elements in the list a. This is done in O(1) time. The first loop enumerates the second list b with the operation append() which is done in O(1) time therefore the first loop is O(n). The second loop I am confused if the sorting plays a factor since I know the sort method is O(nlogn) time. Within the second loop I am a bit confused about the operations as far as what it is specifically doing which I wanted to ask about although I do understand the fact that if the i-th element in a is < c it goes into the if statement.

Space = Overall I think it is O(n) as the only additional space needed was the list x plus the input space and the length of x grows as a or b grows.

Given the following Python code:

a = [3, 1, 2]  # input length will be size n
b = [1, 2, 3]  # input length will be size n
c = 4

def foo(a, b, c):
    res = 0
    if not a:
        return res

    x = []
    for i, j in enumerate(b):
        x.append((j, i))

    for j, i in sorted(x, reverse=True):
        if a[i] < c:
            res += a[i] * j
            c -= a[i]
            res += c * j
    return res

Can someone help go over what the time and space complexity is plus the idea behind it mainly?

  • $\begingroup$ The idea behind what it? space coplexity? $\endgroup$
    – greybeard
    Mar 11, 2021 at 8:27
  • $\begingroup$ This sounds like 3 questions in one post; the site generally works better if you ask only 1 question. For running time analysis, see cs.stackexchange.com/q/23593/755. $\endgroup$
    – D.W.
    Mar 11, 2021 at 8:42
  • $\begingroup$ Sorry everyone, I edited the original post with my thoughts and main questions. $\endgroup$
    – anshur
    Mar 11, 2021 at 9:00
  • $\begingroup$ "additional space needed was the list x plus the input space": this is contradictory, either input space is counted or it is not. In fact, input space does not count in the evaluation of space complexity. $\endgroup$
    – user16034
    Dec 2, 2022 at 9:00

2 Answers 2


You are completely correct in your analysis.

Space. You construct an array $x$ which has length the same as that of $b$, which is $n$. It contains a pair for each element in $b$, so it has size $O(n)$. The other variables do not count, hence space complexity is indeed $O(n)$.

Time. You correctly observed that the sorting of $x$ takes time $O(n \log n)$, and that both iterations take time $O(n)$. Everything else is arithmetic operations, which all run in $O(1)$ time. Hence, something like $O(n) + O(n \log n) + O(n) + O(1)$, which all in all results in a time complexity of $O(n \log n)$.

Well done!

  • $\begingroup$ Awesome! Thank you and that makes me feel pretty good haha! As for the if statement, I am a bit confused there if you don't mind explaining that piece. $\endgroup$
    – anshur
    Mar 11, 2021 at 9:32
  • $\begingroup$ @anshur Let $a$ contain only 0s and $c$ be a very large number, then we will never break, so "worst case" we have to perform all iterations. I don't think there's more to it. The loop itself isn't changed by it, and it's performed in $O(1)$ time. $\endgroup$
    – Pål GD
    Mar 11, 2021 at 10:49
  • $\begingroup$ @anshur feel free to upvote and accept the answer if you are satisfied with it $\endgroup$
    – Pål GD
    Mar 11, 2021 at 16:23

The second loop is indeed tricky. Without a deeper look, it is hard to tell its time complexity tightly, because it could be that the break always occurs very early. But you are on the safe side by assuming $O(n)$ for this loop, which, fortunately, is absorbed by the $O(n\log n)$ of the sort.

The space is indeed $O(n)$, due to the filling of $x$ with $n$ elements, given that appends are done in amortized constant time.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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