Time complexity of Collections.rotate in Java

Question

I haven't found much information about the time complexity of Collections.rotate(list, k), am I correct in assuming the following?

• For ArrayList: O(n) being n the size of the list
• For LinkedList and ArrayDeque: O(k)

Thanks in advance.

Answer 1

IMHO the documentation of Collections.rotate() describes the algorithm nicely:

If the specified list is small or implements the RandomAccess interface, this implementation exchanges the first element into the location it should go, and then repeatedly exchanges the displaced element into the location it should go until a displaced element is swapped into the first element. If necessary, the process is repeated on the second and successive elements, until the rotation is complete.

According to this part of the description the time complexity is O(N) for lists that implement the RandomAccess interface (because for such lists the element access is O(1) and the algorithm needs to access N elements), O(N^2) for lists where the element access is O(N) (for example LinkedList) - but only for small N.

If the specified list is large and doesn't implement the RandomAccess interface, this implementation breaks the list into two sublist views around index -distance mod size. Then the reverse(List) method is invoked on each sublist view, and finally it is invoked on the entire list.

This part of the description is for larger lists that do not implement the RandomAccess interface (for example LinkedList). The description mentions 3 calls to Collections.reverse() and the documentation for Collections.reverse() says:

This method runs in linear time.

That means O(N) for each call to Collections.reverse() - but O(3*N) is a constant factor to O(N) which means that the whole operation for Collections.rotate() also runs in O(N).

---

Note that ArrayDeque does not implement the List interface and you therefore cannot call Collections.rotate() with an ArrayDeque as argument.