CODEWITHSUNDEEP
javaarrays
Ege Kuzubasioglu
Ege Kuzubasioglu

Reputation: 6282

How to reverse an array with huge size?

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) ?

Upvotes: 3

Views: 219

Answers (2)

Sajad Banooie
Sajad Banooie

Reputation: 360

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.

Upvotes: 2

assylias
assylias

Reputation: 328737

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; }
}

Upvotes: 9

Related Questions