CODEWITHSUNDEEP
javascriptarraysalgorithm
Weijing Lin
Weijing Lin

Reputation: 575

What is time and space complexity for concating sorted array by using while loop?

eg. here are two arrays

a = [1, 3]
b = [2, 4, 5]

I used while loop to sort it

var a=[1,3,6,7], b = [2, 4, 5];
var result = [];
var aPointer = 0;
var bPointer = 0;
while (aPointer < a.length || bPointer < b.length) {
  if (bPointer == b.length ) {
    result.push(... a.slice(aPointer));
    break;
  }

  if (aPointer == a.length ) {
    result.push(... b.slice(aPointer));
    break;
  }
  
  if (a[aPointer] < b[bPointer]) {
    result.push(a[aPointer]);
    aPointer++;
  } else {
    result.push(b[bPointer]);
    bPointer++;
  }
}
console.log(result);

I think the time complexity should be O(n + m) = O(n), space complexity is O(m + n + m + n) = O(2(m+n)) = O(2n). Is there better way to concat sorted array?

Upvotes: 0

Views: 129

Answers (1)

trincot
trincot

Reputation: 350272

The code is not completely correct. When all elements from b have been added to the result, and a still has values, then the else block will be executed, resulting in an endless loop of adding undefined to the result array.

Corrected code with different while condition and final concatenation of the remaining "rest" from one of the two input arrays:

var a = [1, 3, 6, 7], b = [2, 4, 5];
var result = [];
var aPointer = 0;
var bPointer = 0;
while (aPointer < a.length && bPointer < b.length) {
  if (a[aPointer] < b[bPointer]) {
    result.push(a[aPointer]);
    aPointer++;
  } else {
    result.push(b[bPointer]);
    bPointer++;
  }
}
result = result.concat(a.slice(aPointer), b.slice(bPointer))
console.log(result);

The time complexity is O(n+m), as each iteration of the loop pushes one value to the result, and the result will in the end have n + m values. The final concat and slice is just a short way to do the same for the remainder of one of the two input arrays. So the time complexity is not influenced by it.

The space complexity is usually expressed only in the extra space used, so not including the space used by the input. So apart from some constant space used by atomic variables (such as aPointer), there is the result array, which takes O(n+m) space.

Upvotes: 1

Related Questions