Isn’t the space complexity in that example O(n) where n is the number of elements in the sequence? Because we do create a new array ‘result’ where we append the values. If k < len(sequence) the space complexity O(n) right?
Space complexity in 10.3 Sort an almost sorted array
Fennel
#2
Update: Nope, i take it back. It should definitely be O(n). If they’re counting ‘n’ in the time complexity, then they should be counting it for the space as well given the size of the output list is directly proportional to ‘n’.
I came here to say the same thing. Here’s one possible explanation that crossed my mind. Since the input is an iterator (reference to a start) and not the collection itself, the output is not technically dependent on the size of the input itself. So maybe that’s the caveat? Even though we’re creating and returning a list of the elements of that sequence?
0 Likes