AtomicStrongForce AtomicStrongForce - 1 year ago 125
Java Question

Runtime of Arrays.copyOfRange()

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 Source

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.