AtomicStrongForce - 6 months ago 68

Java 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

`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.