Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the time complexity of this in-place array reversal?

Is this function O(n) or O(log(n)) time complexity.

function reverse(array) {
  for (var i = 0, j = array.length - 1; i < j; i++, j--) {
    var temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }

  return array;
}

At first glance it appears to be making n/2 iterations over the input. However, if you think about it, the actual number of lower level operations is closer to 2n.

like image 438
Eric Rini Avatar asked Jan 04 '23 23:01

Eric Rini


1 Answers

So assume you have a string of length n Then you have indicators i=0, and j = n-1 The loop continues until i>=j with j decrements by 1 and i increments by 1 This will give you a total of n/2 iterations. Inside the loop you have a total 3 statements meaning the loop will complete a total of 3(n/2). Along with that you have 1 operation outside the loop leaving us with

f(n) = 3(n/2)+1 which is O(n)

EDIT: This assumes that the loop maintaining operations(i++,j--) are trivial which is common practice when dealing with Big Oh notation

like image 177
Garrigan Stafford Avatar answered Jan 08 '23 06:01

Garrigan Stafford