Could you tell me please, if I use for i in range(n), does python creates a range of 0 .. n-1, and iterates elements in this container (O(n) extra space), or it use only 1 vatiable (O(1)) space)
From one side, I thought, if we can convert range to list, then using range function creates a container (O(n)).but from the other side, instead of using for i in range(n), we can use while i < n ... O(1).
In Python 3, range does not create all the elements, but only returns the current element when you request it. So yes, it's using O(1) space.
It's O(1): the range object doesn't store the values it yields.
As the Python documentation explains:
The advantage of the
rangetype over a regularlistortupleis that arangeobject will always take the same (small) amount of memory, no matter the size of the range it represents (as it only stores thestart,stopandstepvalues, calculating individual items and subranges as needed).
Of course, if you make a list with the contents of the range, the list does use O(N) space.
This was one of the big changes between Python 2 and Python 3. In Python 2, range created a full list, but you could avoid creating a list by instead using xrange. So in Python 2, you'd do for i in xrange(...) to efficiently iterate over a range without creating a temporary list.
In Python 3, this was changed so that range behaves like the Python 2 xrange. To get the Python 2 range behavior in Python 3, i.e. to create the full list, you can do list(range(...)), but of course you want to avoid that unless you truly need the list.
