Menu
I have a question if whether the following code is executed in place or has extra space complexity. Given that sentence was a string initially. Thanks appreciate the help
sentence = "hello world"
sentence = sentence.split()
375
We shall then split the string by space using String.split () method. split () method returns list of chunks. In this example, we will take a string with chunks separated by one or more single space characters. Then we shall split the string using re.split () function. re.split () returns chunks in a list.
To understand the time and space complexity of a function in python, it is important to understand the underlying algorithm’s implementation that the function actually uses. Before that, we first need to know what CPython is. CPython is the original Python implementation written in C. It is also the implementation we download from Python.org.
Since swap is a constant time operation, the overall time complexity is O (N/2), which is same as O (N). Space Complexity: O (1) – As you can see in the CPython function, there’s no auxiliary space involved and there’s no use of recursion either. Hence the space complexity of the operation is constant i.e O (1).
Time complexity: O (n^2) where n is the length of the input string. This is because in every loop iteration, the string concatenation of new_word gets longer until it is at worst, length n.
In python strings are immutable objects, which means that they cannot change at all "in-place". All actions on them essentially take up new memory space, and hopefully, the old unused ones are deleted by python's garbage collecting process (if there are no more references to those objects). One method to see it for yourself is this:
>>> a = 'hello world'
>>> id(a)
1838856511920
>>> b = a
>>> id(b)
1838856511920
>>> a += '!'
>>> id(a)
1838856512944
>>> id(b)
1838856511920
As you can see, when b and a are referring to the same underlying objects, their id in memory is the same, but as soon as one of them changes, it now has a new id - a new space in memory. The object that was left unchanged (b) still has the same place-id.
To check it in your example:
>>> sentence = "hello world"
>>> id(sentence)
1838856521584
>>> sentence = sentence.split()
>>> id(sentence)
1838853280840
We can once again see that those objects are not taking the same memory. We can further explore just how much space they take up:
>>> import sys
>>> sentence = "hello world"
>>> sys.getsizeof(sentence)
60
>>> sentence = sentence.split()
>>> sys.getsizeof(sentence)
160
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
