How would you traverse a linked list in O(n^0.5)?

This is an interview question of开发者_JS百科 Apple. I have found no convincing argument in support or against it yet.

---

Traversal more efficient than O(n) is not possible, since "traversal" requires accessing each node in turn.

It is possible to make random access faster than O(n) though, by maintaining a second linked list that retains links to intermediate nodes; insertion, deletion, and appending cost will go up though, due to the increased complexity of maintenance of the second list.

---

Not possible.

This is assuming you mean look at every node in a linked list of n nodes. It's probably a trick question to see if you can figure out that it isn't possible.

---

When I first encountered this question, I thought the same thing as most people here: it's impossible, a trick question, a psychological test of some kind. I was wrong.

The real answer is that it IS possible to traverse a list faster than O(N), at least theoretically, using a quantum computer.

Check out the Wikipedia article for Grover's algorithm here.

They state an amortized running time of O(n^0.5), and space of O(log n). It also should be noted that it is not deterministic. That means that there is high probability that the algorithm will return the correct result, but it is not guaranteed.

I'm guessing that is enough to pass the question, but the rest is over my head.

Best of luck.

---

Perhaps if every node has a connection to the next element, previous element, and a center element (where center is the mid point between the current element and the end of the list).

Thoughts?