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
    Commented Mar 8, 2021 at 20:04
  • $\begingroup$ a and b. Is there a better way to ask that shows those to be n $\endgroup$
    – kasuf
    Commented Mar 8, 2021 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
    Commented Mar 8, 2021 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
    Commented Mar 8, 2021 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
    Commented Mar 9, 2021 at 6:55

1 Answer 1

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
    Commented Mar 8, 2021 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
    Commented Mar 8, 2021 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
    Commented Mar 9, 2021 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
    Commented Mar 9, 2021 at 0:16
  • $\begingroup$ Awesome, that is what I thought. Thanks! I upvoted but it can't be seen apparently. $\endgroup$
    – kasuf
    Commented Mar 9, 2021 at 0:19

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.