Runtime of Arrays.copyOfRange()

Question

What is the big-O runtime of Java's Arrays.copyOfRange(array, startIndex, endIndex) function?

For example, would it be equivalent or less efficient in terms of both space and time complexity to write a simple binary search on arrays function using copyOfRange rather than passing in the start and end indices?

Answer 1

Arrays.copyRangeOf() uses System.arraycopy() which uses native code (could use memcpy for example - depending on JIT implementation) under the hood.

The "magic" behind copying with System.arraycopy() is making one call to copy a block of memory instead of making n distinct calls.

That means that using Arrays.copyOfRange() will definitely be more efficient comparing to any other solution you'll choose to implement by yourself.

Further, I don't see how a binary search could help here: an array has a direct access - and here we now exactly what are the src, dst and how many items should we copy.

From big-O perspective, the complexity will be O(n*k) where n is the number of items to copy and k is the size (in bits) of each item. Space complexity is the same.