How to reverse an array with huge size?

Question

Ok so I know it's really easy to reverse an array by swapping items up until you reach the middle. Like this:

int array[SIZE];
int temp;

for (int i = 0; i < SIZE/2; i++)
  {
     temp = array[i];
     array[i] = array[SIZE-1 - i];
     array[SIZE-1 - i] = temp;
  }

But what if the array size is really huge like 10000? Is it possible to do it O(N) ?

You're doing it O(N) right now. The whole point of O() is that it N is unspecified. — Jonathon Reinhart, Dec 30 '16 at 12:41
the code you have written is already a O(n). More precisely it runs n/2 iterations. — Shubham Chaurasia, Dec 30 '16 at 12:41
Ok I got it but what if the size equals to 1000000, wouldn't this method take too long? — Ege Kuzubasioglu, Dec 30 '16 at 12:42
[How do I write a correct micro-benchmark in Java?](http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) :) — sp00m, Dec 30 '16 at 12:44
If you used Lists rather than arrays you could write a view that views a list in reverse in O(1). `com.google.common.collect.Lists.reverse` does this already. — cpp beginner, Dec 30 '16 at 12:46
Thanks, I heard about *Commons.Lang* library `ArrayUtils.reverse(int[] array)` , is it possible to use it for string arrays? — Ege Kuzubasioglu, Dec 30 '16 at 12:50

score 9 · Accepted Answer · answered Dec 30 '16 at 12:45

You can't do it faster than your current algorithm, which runs in O(n). What may be of interest is to wrap your array in a class that provides an O(1) reversal:

A simplistic version could look like this:

public class ReversableArray {
  private boolean reverse = false;
  private final int[] array;
  public ReversableArray(int[] array) { this.array = array; }

  public int get(int index) {
    return reverse ? array[array.length - index - 1] : array[index];
  }
  public void reverse() { reverse = !reverse; }
}

score 1 · Answer 2 · edited Jun 20 '20 at 09:12

reversing an array cant be done any faster than O(n).However the time complexity of your code is O(n) too.

the definition of Big-Oh: f(x) is Big-Oh of f(x) if:

definition of Big-Oh

is not infinity

or we can say that: alternate definition for Big-Oh

there exits a constant c such that c.f(x) is bigger than g(x) for all values of x.

here we consider,n the size of our array and the function T(n) the steps of our program.

swapping tow integers costs constant time.doing swaps n/2 times will result O(n).

and sorry for not including images in the answer.

How to reverse an array with huge size?

2 Answers2