0

What is the space complexity of splicing list in python if we are using it for calculating sum? and we are not assigning a list to anything.

a = [1,2,3,4]
sum_except_first = sum(a[1:])
Akshay
  • 1
  • 2
    It's O(n), with n being the length of your list – Riccardo Bucco Aug 30 '22 at 16:46
  • But we are not assigning a list to anything just using it for sum? – Akshay Aug 30 '22 at 16:47
  • 2
    You assign it to the parameter you pass into `sum` – luk2302 Aug 30 '22 at 16:47
  • 2
    You're still creating it, even if you don't assign it to any variable – Riccardo Bucco Aug 30 '22 at 16:47
  • Space and time complexity do not care if you actually use the thing you loop over or create as long as you loop or create it counts. It is up to you to not create / loop unnecessary things. Here obviously it is necessary to create the slice and therefore it counts, what you do with the slice is irrelevant. – luk2302 Aug 30 '22 at 16:49
  • To reduce the space I can take sum(a) and subtract it from first element to get remaining sum right so then space wont be used? – Akshay Aug 30 '22 at 16:51
  • `sum(a) - a[0]` would for example have better space complexity. A for loop that starts at index 1 instead of 0 would also perform better. – luk2302 Aug 30 '22 at 16:51
  • So using sum(a)-a[0] will do it in constant space right? – Akshay Aug 30 '22 at 16:53
  • Probably, not sure how `sum` is implemented but I would hope it is smart. – luk2302 Aug 30 '22 at 16:54
  • What if we do not want to consider a in space considering it is a leetcode problem where a is passed as param and that is not included in space complexity calculation – Akshay Aug 30 '22 at 16:56
  • Sum if inbuilt python function that I am using – Akshay Aug 30 '22 at 16:57
  • it's linear. whether or not you assign the resulting list to a variable is irrelevant, it is still created – juanpa.arrivillaga Aug 30 '22 at 17:16
  • If `a` is the input then you can compute its sum in constant space, yes. – luk2302 Aug 30 '22 at 17:17
  • @luk2302 so even if we use splicing and a is the input it is constant space right? – Akshay Aug 30 '22 at 17:26
  • the question is answered here: https://stackoverflow.com/questions/5131538/slicing-a-list-in-python-without-generating-a-copy – D.L Aug 30 '22 at 17:40
  • Does this answer your question? [Slicing a list in Python without generating a copy](https://stackoverflow.com/questions/5131538/slicing-a-list-in-python-without-generating-a-copy) – D.L Aug 30 '22 at 17:41
  • I saw the link but even if the reference of element is stored the sliced list new memory would be required as if we update the sliced list main list is not updated right? – Akshay Aug 30 '22 at 18:34
  • Then it depends on your definition and the way you measure it - overall you could argue it takes 2n space, one n for the input, one n for the slice, therefore O(n). Or just one n for the slice if you disregard the input. If you then optimize the slice away you end up either with one n (still O(n)) or zero n (would be O(1)) – luk2302 Aug 30 '22 at 19:49
  • Yup. If you dont consider input slice would be still O(n) if I remove slice and do sum(a)-firstelem then it would be constant – Akshay Aug 30 '22 at 22:45

0 Answers0