I don't understand how linked list insertion is constant time. The larger the list gets, the more bits are required to specify memory locations, and then the more bits that must be edited to account for changes in pointers.
Where is my mistake here?
$\begingroup$
$\endgroup$
-
$\begingroup$ Do you use RAM model? How many pointers do you move during inserton? What is the size of the pointer? $\endgroup$ – Evil Apr 20 '18 at 21:26
-
$\begingroup$ I'm not sure I'm afraid. I'm thinking about Turing machines, but I don't know if that matches what you refer to. $\endgroup$ – John Smith Apr 20 '18 at 21:29
-
$\begingroup$ Basically, I have an algorithm where we maintain a list of constraints. I want to use a linked list so that the constraints can be added in constant time, but I'm worried that, as the number of elements of the list increases, eventually we will need pointers larger than, say, 4 bytes, so I can't say it's constant time maybe. $\endgroup$ – John Smith Apr 20 '18 at 21:30
-
1$\begingroup$ en.wikipedia.org/wiki/Transdichotomous_model $\endgroup$ – D.W.♦ Apr 20 '18 at 21:55
-
$\begingroup$ THANK YOU. I must say it seems like a bit of a hack, but what a relief there's a simple workaround. $\endgroup$ – John Smith Apr 20 '18 at 22:01
$\begingroup$
$\endgroup$
We usually analyze algorithms using the RAM model, in which basic operations on machine words cost $O(1)$. On an input of length $n$ bits, the size of a machine word is $\log n$. In your case, a pointer should fit into one machine word, and so moving a pointer should take $O(1)$ time.
A different issue is how much time is required to maintain the heap. One way around this is to work in the "heap-enabled RAM model", in which heap operations are for free. Probably many papers on algorithms implicitly work in this model.
Finally, a few words on the RAM model. It extends the Turing machine model in two ways. First, it allows indexing. This matches the way actual computers work. Second, it allows constant time arithmetic on machine words, which are usually chosen as indicated above. The size of machine words is chosen so that operations on indices take $O(1)$. For example, consider the following program for summing an array $A$:
sum = 0
for i from 1 to n:
sum = sum + A[i]
return sum
If we want this algorithm to run in $O(n)$, we need the operation $i \to i + 1$ to run in $O(1)$. Since $i$ could be $\log n$ bits long, we need machine words to be at least $\log n$ bits long. Practice shows that it is not necessary to consider larger machine words. Note that machine words of size $C\log n$ can be simulated using $O(1)$ machine words of size $\log n$ using a multiplicative overhead of $O(1)$; since we don't care about constant factors, increasing the machine word to size $C\log n$ doesn't affect the power of the model.
answered May 21 '18 at 13:05
$\begingroup$
$\endgroup$
Existing computers have fixed sized pointers, so this problem is ignored.
Now I design a computer that works as follows: It follows instructions as usual. If it needs more memory than available, then it has a printer and a little robot attached, the printer orders more memory, the robot sends the order to Amazon and puts the memory into the computer. And if it needs so much memory that the pointer size isn't big enough, then the little robot constructs a new computer with doubled pointer size and the new computer continues running the program.
On this computer, it takes O (log n) to insert the nth pointer to a list. Well, not quite, because the size of the universe is limited, so you need a slightly bigger robot that creates bigger universes as needed.
