educative.io

Educative

Time complexity with for loop and splice

What would be the time complexity for the following code? Is it O(n^2)? Because for loop is O(n), inside the for loop there is splice(), and splice() is O(n) as well. So the time complexity will be O(n^2)? Please correct me if I’m wrong. Thanks!

Here is the code snippet:

function removeEven(arr) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] % 2 === 0) {
            arr.splice(i, i);
            i--;
        }
    }
    return arr;
}

I’m also on this topic and having a similar answer:

Summary
function removeEven(arr) {
              let i = 0;
              while(i < arr.length){
                if(arr[i]%2 == 0){
                    arr.splice(i, 1);
                }else{
                    i++;
                }
            }
            return arr;
        }

I feel you don’t need to consider the time complexity of splice(), so it should be O(n).

You are absolutely right Tina. The time complexity of your solution will be O(n^2). First we are using the for loop for traversing the array elements and within the for loop we are using the splice() function. splice() adds or removes element in the original array. Therefore, in the worst-case, we have to shift n−1 elements.

Maida Ijaz | Developer Advocate
educative.io