Is passing an array slice to a function in Python an O(1) or O(N) operation?

Question

I have a function that takes an input string of characters and reverses them according to the white space breaks.

For example:

input:  arr = [ 'p', 'e', 'r', 'f', 'e', 'c', 't', '  ',
                'm', 'a', 'k', 'e', 's', '  ',
                'p', 'r', 'a', 'c', 't', 'i', 'c', 'e' ]

output: [ 'p', 'r', 'a', 'c', 't', 'i', 'c', 'e', '  ',
          'm', 'a', 'k', 'e', 's', '  ',
          'p', 'e', 'r', 'f', 'e', 'c', 't' ]

To reverse the 'words', I use the following function

def reverse_word(arr):
  i = 0
  j = len(arr) - 1
  while i < j:
    arr[j], arr[i] = arr[i], arr[j]
    i += 1
    j -= 1
  return arr

def reverse_words(arr):
  
  arr.reverse()
  p1 = 0
  
  for i, v in enumerate(arr):
    if v == ' ':
      if arr[p1] != ' ':
        arr[p1:i] = reverse_word(arr[p1:i])
      p1 = i + 1
  
  arr[p1:] = reverse_word(arr[p1:])
  return arr

My question is: Is the call to reverse an O(1) or O(N) space operation? I assumed O(N) but someone else said it was O(1). I assumed O(N) because in the worst case, with one word, the entire array will need to be copied to the stackcall. Space is not "constant" because the space size allocated to the call is dependent on the input length.

This is a little confusing because you have two functions called `reverse` here: `arr.reverse()` and the function you defined. Also, it looks like you have a typo in the reverse function — you are incrementing both `i` and `j` at the same time. How will that loop ever end? — Mark, Nov 15 '20 at 22:14
I'd you wanted to make the whole algorithm constant space you could pass in the whole list, and the indices within which you reverse it, so something like `reverse_word(arr, i, j)` — juanpa.arrivillaga, Nov 15 '20 at 23:34

score 0 · Answer 1 · answered Nov 15 '20 at 22:18

0

To answer your question first: Yes the reverse function you defined is an O(1) space operation(even though it's wrong and will never end). The reason is, when you pass in a list to the function in python, it does not copy the whole list, it passes it's reference(or the pointer, if you are familiar with C concepts). So no matter how long your array is, the space usage is constant.

However, your question alone may be meaningful, but in this program, it does not matter. We all know for an algorithm, the big-O for space and time is determined by the largest part of the algorithm. You actually other operations in your code that has O(N) space operation. For example, reversed() function generates a whole new list.

BTW, it's not the best practice to define a function that has the same name with other methods you may use(in this case, reverse).

answered Nov 15 '20 at 22:18

minker

510
6
3

Thanks. Yes I realize the function is not well named; did this for demonstration; and I fixed the bug. What's confusing is: Why is it O(1) space when the length of space needed is variable and dependent on the fraction of the list that's passed? In some cases the entire list will be passed and it should be O(N), no? Shouldn't constant space always require a.. constant amount? You say it's passing a pointer, which I understand. But I thought the slice indexing passed a copy of the allocated memory. I realize the other operations are O(N) but just focusing on this one part. – Union find Nov 15 '20 at 23:09
1

OK I see, "Slicing lists does not generate copies of the objects in the list; it just copies the references to them. That is the answer to the question as asked." This is the point of confusion for me. I will need to understand this better. This is the crux of the matter no? We're using already allocated space and merely modifying pointers. – Union find Nov 15 '20 at 23:15
A clarification: Python passes _everything_ by object reference (which is similar, but not quite identical, to pass by reference), not just lists. – Kirk Strauser Nov 15 '20 at 23:17
Thansk @KirkStrauser. It seems like you're making two assertions: It's not just lists that do this but all data structures. And secondly, it's by object reference specifically, and not just by reference. Is that correct? – Union find Nov 15 '20 at 23:24
A slice of size N requires O(N) space an O(N) time – juanpa.arrivillaga Nov 15 '20 at 23:27
@Learningstatsbyexample yes, python uses a single evaluation strategy, which is neither call by reference nor call by value, regardless of the type – juanpa.arrivillaga Nov 15 '20 at 23:28
Well now I'm confused. So it does need additional space or doesn't? It seems like copying the references would require additional space. @juanpa.arrivillaga – Union find Nov 15 '20 at 23:29
Yes slicing require linear space and time. – juanpa.arrivillaga Nov 15 '20 at 23:30
So, your `reverse_word` function operates in constant space, but you create a new list and pass it to the function, which requires linear space – juanpa.arrivillaga Nov 15 '20 at 23:32
Oh yes.. that is what I assumed. Thanks. So this answer by @minker doesn't really get at the question I was curious about, which is whether *passing* the slice in this way is a constant time operation. The swapping of elements in the reverse_word function obviously is O(1) time as it just is a two pointer movement. – Union find Nov 15 '20 at 23:37
@Learningstatsbyexample yes, I think the OP was basically think that you were asking "is python call by value", which it isn't (again, it isn't call by reference either). An expression you provide to an argument in python is always fully evaluated before the resulting object is actually passed, so saying "I passed a slice" might be a bit confusing. You passed a list, which was the result of your slicing operation (which is just syntactic sugar for a `list.__getitem__` call) – juanpa.arrivillaga Nov 15 '20 at 23:43
@juanpa.arrivillaga do you want to generate your own answer/ I will accept. Do you recommmend any reading on this topic? I will be searching. – Union find Nov 15 '20 at 23:52
1

@Learningstatsbyexample, yes slicing itself is an O(N) O(N) operation. Technically, _passing_ the slice is still an O(1) operation, but _generating_ the slice is O(N). You have two steps here. If you separate them like `s = arr[p1:i]` then `reverse_words(s)`, the function still is an O(1) operation. So when you say the _call_ to `reverse_words`, I would assume that you meant when you _call_ the function, not _preparing_ the arguments. But there's way to avoid that as well as in your comment :) – minker Nov 16 '20 at 00:19
@minker when you say: 'But there's way to avoid that as well as in your comment :) ' what do you refer to? just performing the operation in place without creating the slice? – Union find Nov 16 '20 at 00:22
@Learningstatsbyexample, that's right. Like juanpa.arrivillaga mentioned, you can do it without creating the slice. You can pass in the array itself, and the index of start and end element. This way you can do the swap in place. Passing the array is an O(1) operation, so is passing the indexes. That is a solution with better performance. However, I still stand on my point that, academically, we can discuss every single bit of the algorithm we want and that's fun, but practically, you need to think about the tradeoffs (mostly performance vs cleaner code) when you implement. – minker Nov 16 '20 at 00:46
this was just created for stackoverflow.. @minker. but yes i hear you. if you passed in the full array and assigned it back to the same arr, that would simply modify the pointers and not use more space, right? – Union find Nov 16 '20 at 00:48
1

@Learningstatsbyexample that's correct. You don't need to return the array, you can just do it in place. Do something like `reverse_words(arr, start_idx, end_idx)` and do the swapping in the function. – minker Nov 16 '20 at 01:05
This chat is getting very long. @Learningstatsbyexample, see my answer at https://stackoverflow.com/questions/13299427/python-functions-call-by-reference/13300388#13300388 about why it's not by-value and not quite by-reference. But yes, passing arguments to a function is constant time, as what you're passing is a pointer to the value you're passing in (_not_ the variable that refers to the value; see my link for more info). – Kirk Strauser Nov 17 '20 at 01:13
@KirkStrauser yes got it. I read ch. 3 of the python reference docs on the object model, which clarified. furthermore, i read on pass by object reference. it was the slice that made this o(n) but not the object reference creation for the call. – Union find Nov 17 '20 at 01:57

Is passing an array slice to a function in Python an O(1) or O(N) operation?

1 Answers1