2

I'm trying to understand how slicing works in Python. If I do something like

arr = [1,2,3,4,5]
arr[0:n] = [9]*n

What is the runtime of a splice operation where n is some integer? Does this this run in O(n), or is slicing somehow constant time?

2
  • All this does is multiply 9 by n and then raise an exception, so its runtime is constant. Nov 4, 2014 at 1:19
  • @ChrisMartin very funny, thanks for pointing this out. Edited.
    – Apollo
    Nov 4, 2014 at 1:31

2 Answers 2

0

You should try the IPython notebook and it's %%timeit magic which makes timing things easy. I think I understand what you're trying to do, so I sliced a list of 500 elements vs. 5000 a list of 500 elements. Is this what you ahd in mind?

enter image description here

Unless my analysis is wrong, this looks order N?

2
  • Your analysis is wrong. You're timing the creation of arr, not just the replacement of n of its elements. (that being said, both are O(n))
    – Max Noel
    Nov 4, 2014 at 2:46
  • Thanks, I will correct it, but OP should be able to do this trivially with %%timeit in the notebook. Nov 4, 2014 at 16:12
0

There is no way that's constant. The expression [9]*n alone is linear in space, and therefore also in time.

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.