1

I am learning data structure and pretty new to this game. I know a single loop running for n-iteration has O(n) time complexity. But if I use a splice inside the for loop, is it going to be O(n2) time complexity? I am positive it's O(n2) but want to make sure.

Here is the sample code that I was working on:

var createTargetArray = function(nums, index) {
    let target = []
    for (let i=0; i< index.length; i++){
        let idx = index[i]
        target.splice(idx,0,nums[i])
    }
    return target
};
Richard Barber
  • 5,257
  • 2
  • 15
  • 26
Muazzam Nashat
  • 11
  • 1
  • 1
    The call to `.splice()` is basically a "hidden loop", so yes I'd call that n² – Pointy Mar 04 '21 at 18:12
  • These two links will be really helpful - [Understanding JS arrays and splice](https://stackoverflow.com/questions/37157916/understanding-js-arrays-and-splice) and [What's the time complexity of array.splice()](https://stackoverflow.com/questions/5175925/whats-the-time-complexity-of-array-splice-in-google-chrome) – Mike B Mar 04 '21 at 18:23
  • Although `splice` might be a "hidden loop", since you only use it to add a single element at a time, the worst performance you can get is by adding each new elements in the first position (aka `unshift`), thereby shifting all other elements one index up. I am not sure what the time complexity of [`unshift`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/unshift) is, so I'll leave that up to you/others to find. – 3limin4t0r Mar 04 '21 at 18:39

2 Answers2

0

You are correct. Worst case for the splice method should be O(n). That call is occuring inside the iteration of a foreach loop O(n); So the big o-notation of the whole script is O(n^2)

Ran Turner
  • 14,906
  • 5
  • 47
  • 53
0

Since big O notation is asking how many iterations your function takes to perform f(x) to your array as input, when you loop over all the elements the general time complexity of O(n). However using the .splice() function in JavaScript also has ideally a time complexity of O(n) and thus when you put a O(n) in another O(n) then it effectively becomes O(n^2). As a good rule of thumb you can think of nested O(n) increasing the power of n by one . For example if you were to loop to have a triple nested loop doing 1 operation to each element of an array it would become O(n^3) and so on.

Anas_Adeel
  • 1