I have a situation where I have a determinate input range and as such, am able to do indexing entirely in O(1) by creating a list that is the size of the range of the input and indexing the input by itself. To be clearer, I essentially have the following situation
a = "inputrange"
rng = ord(max(a)) - ord(min(s))
data = [None] * rng
My issue is, I'm not sure if the allocation process for data is O(1) or not. Intuitively, there should be some way to do it in O(1), as on the stack I'm simply defining a start and end point for the data, and as such should only take O(1) time to allocate, but python is a bit removed from this so I can't be sure.
It's very important I can allocate in O(1), as I am creating a suffix tree for the input data, and so to ensure O(1) indexing when traversing the tree I need a list the size of the alphabet (or a hashmap, although I'm avoiding those), but since I'm allocating essentially for every suffix, I need allocating to be constant.
Another idea I had was to create a "template" list and copy that over, but copying takes O(n) time so that won't work.
EDIT: This isn't a duplicate of "what is the time complexity of [var]*n", I clearly state I am looking for a way to do to list memory allocation in O(1). Just because I happen to be using [var]*n as my current method of allocating this memory, does not mean it is answered by knowing the complexity of this method.
The question still remains: Is there a way of allocating space for an empty list in python in O(1) time