1
$\begingroup$

Can anyone help me understand the time and space complexity here? I know zip() is O(1) and sorted() is O(n). The loop has the operation min() inside but is operating on just 2 values so is that also O(1)? If so then every operation in the loop is O(1) so the overall time complexity is O(n) correct? For space, z could grow to n as a and b grow to n as well so space is O(n)?

a = [3, 1, 2]
b = [1, 2, 3]
c = 4
def foo(a: list[int], b: list[int], c: int) -> int:
    ans = 0
    if not a:
        return ans
    z = sorted(zip(a, b), reverse=True)
    for x, y in z:
        if c > 0:
            x = min(x, c)
            ans += x * y
            c -= x
    return ans
$\endgroup$
6
  • 1
    $\begingroup$ What's $n\phantom{}$? $\endgroup$ – Steven Mar 8 at 20:04
  • $\begingroup$ a and b. Is there a better way to ask that shows those to be n $\endgroup$ – kasuf Mar 8 at 20:44
  • $\begingroup$ The notation $O(n)$ only makes sense if $n$ is an integer (or at least a real number). a and b are lists. $\endgroup$ – Steven Mar 8 at 20:47
  • $\begingroup$ Oh, okay. So I mean the size of a and b. So if the input size, which is the list length, grows to infinity then the behavior of the function as depicted on the graph is telling of the efficiency of the function. $\endgroup$ – kasuf Mar 8 at 20:51
  • $\begingroup$ sorted() $\in O(n)$? The time required by sorted is bounded below by the number of items. Please substantiate your proposition that is an upper bound, too. $\endgroup$ – greybeard Mar 9 at 6:55
2
$\begingroup$

Assuming that sorted() really takes time $O(n)$, then the time and space complexities are indeed $O(n)$. Hoewever there are some catches.

You say that the zip function takes $O(1)$ time. This is technically true, but you should be aware that zip is not creating a list that contains pairs of elements from a and b but just returning an iterator to these pairs. Going through the list implicitly returned by this iterator takes $O(n)$ time, even just to construct it (e.g., list(zip(a,b))). In your particular case this doesn't really matter since the time complexity will be $\Omega(n)$ anyway.

You say that sorted() takes $O(n)$ time. This is not impossible, but it's at least suspicious (have you checked in the python documentation/implementation?). There is no algorithm that can sort a list of $n$ elements in time $O(n)$ by only performing comparisons. The implementation of sorted() would need to be particularly clever and recognize that you are sorting small integers.

Probably sorted() just takes $O(n \log n)$ time and $O(n)$ space, which would result in the same overall time and space complexities for your algorithm.

$\endgroup$
5
  • $\begingroup$ Wow, I have looked at sorted() and I knew it was O(nlogn) due to TimSort. I apologize for the confusion as I forgot. The iterator part makes sense. And just to clarify then you are saying both overall time and space are O(n) but just explaining a bit further why $\endgroup$ – kasuf Mar 8 at 22:04
  • $\begingroup$ If sorted() takes time $O(n \log n)$ then the time complexity is $O(n \log n)$ and the space complexity is $O(n)$. $\endgroup$ – Steven Mar 8 at 23:45
  • $\begingroup$ Final question, and thanks for all your help. So even though it is looping through the sorted iterator of length n, it is still O(nlogn)? I would have thought O(n) at that point. $\endgroup$ – kasuf Mar 9 at 0:14
  • $\begingroup$ If you're just asking about the complexity of the loop after the list has been sorted, then it's $O(n)$. If you're asking about the complexity of the whole algorithm then its $O(n \log n)$ since you're spending $\Theta(n \log n)$ time (in the worst-case) just to sort the list. $\endgroup$ – Steven Mar 9 at 0:16
  • $\begingroup$ Awesome, that is what I thought. Thanks! I upvoted but it can't be seen apparently. $\endgroup$ – kasuf Mar 9 at 0:19

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.