Suppose a list of five element are there . a = [1,2,4,5,6] . and i want to insert element 3 in between , so what will happen if i use insert func of python .
If option 1 , then why time comp for insert() func is o(n) in python , not o(1)
Solution 2 is correct- it will take more memory.
Python has pointers for everything. So when you create a list, say foo = [3, 4, 5], python attaches a unique id to this list, foo, and points each index (position) in the list to the id of the value at the index.
When you do foo.insert(add_index, val), you are changing the pointer for all indices after add_index. This is why the time complexity is O(n), since n pointer may need to be changed depending on the add_index variable.
Memory doesn't scale linearly with what you are adding. The memory used by a list depends on what is being added (str vs float vs int ...) and whether the element is unique (create new pointer vs reference old pointer). In your case, it's correct that the list will approximately take (6/5) times the memory.
