Time complexity

1 
let arr = [10,20,40,100];
let result= [ ];
let i =2;

//Time complexity of this loop is O(n +1)
while(i<arr.length){
   result.push(arr[i]);
 }

**//Time complexity of this ???**
if(i<arr.length){
   result.push(...arr.slice(i));
  }

Here is what i think : Since spread and slice are inside push first it will perform slice and then spread then push so is it O(N + N +1) or something else ??

2

I’ve edited your post for readability. When you enter a code block into a forum post, please precede it with a separate line of three backticks and follow it with a separate line of three backticks to make it easier to read.

See this post to find the backtick on your keyboard. The “preformatted text” tool in the editor (</>) will also add backticks around text.

Note: Backticks are not single quotes.

markdown_Forums

1 Like
3

Hello, DVGY.

I do not understand what your question is, but you have a few issues in your code.
while (i < arr.length)
You are never incrementing i, and arr.length is remaining the same. So, this is an infinite loop.

What do you mean by “time complexity”? What is the purpose of this code?

4

Putting aside what @Sky020 says, O(N + N + 1) is just O(N)

5

Sorry i forgot to put i++. Let’s say we have array of 100,0000 numbers.

Time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input. But here i have a

while(i<arr.length){
  result.push(arr[i]);
i++;
}

and

if(i<arr.length){
   result.push(...arr.slice(i));
  }

In simple terms which runs faster ???

Thanks

6

The first one is faster, probably much faster, as the spread operation being fast depends on optimisations being made in the underlying JS engine being used when interacting with an Iterator (ie if the operation in the iterator can be rewritten to a while loop, which it won’t be in any JS engine afaik).

Edit: I don’t understand what you’re doing here, you’ve added extra stuff to the second one that’s pointless. And complexity is the same anyway unless you start unpicking all the steps a specific JS implementation goes through to do a specific set of things.

It should just be:

return arr.slice(i);
// or result = arr.slice(i);

Why are you using push/spread? With above it should be almost exactly the same in terms of speed. A simple while loop [for this very specific thing] is basically the lowest level thing you can do, but you don’t know exactly what optimisations the JS engine will make based on the size/contents of the array, so slice could well be faster dependent on implementation.

Also, all you’re really doing is removing the first few entries from an array. If you’re really trying to work out the fastest way to do this (and this is a trivial example, and it’s in an extremely high level language, so it’s a bit of a fool’s errand), then just remove the first few entries instead of copying to a new array. The array has to be reindexed, but that’s much, much faster than creating a new array.

7

Thank you . You answered well.

I was implementing Merge Sort. check line number 21 to 29. So i asked you the above question thanks.