Understanding Javascript array methods Time complexity (BIG O Notation).

This is my first post, i hope you learn something.

To explain big o notation, let me use an example, lets say we have to solve a problem or build something, we need an algorithm, algorithm is just a step by step instruction telling the computer what to do.

Most of the time if not all the time, there are more than one way for getting the desired result, wont it be nice if there is a way of comparing two or more algorithm to know which one is better.

This is exactly what BIG O Notation does. it basically compares using the time complexity or space complexity.

It is not perfect but it gives us a simplified view of the worst case scenario when comparing two algorithm or knowing how good your current solution or algorithm is doing.

I will list and discuss some of them briefly

Constant Time O(1) - When you code an algorithm and it runs in the same time or space regardless of the inputs you used. We can say that the algorithm runs at constant time.

What javascript array methods runs at constant time?

1. PUSH
2. POP

Push adds an item to the end of an array
Pop removes an item at the end of an array

Since both actions do not affect the index of the array in anyway they are done at constant time which means that, it does not matter how large an array, the time it takes to remove and add an item will always be the same.

Linear time O(N) - When you code an algorithm and the time or space it takes to run is directly proportional to the inputs used. This means that increasing the inputs of the algorithm will increase the time or space it takes to run. For illustration purposes, if using an array with 10 items will take 1 minute to run, using an array wit 20 items will take 2 minutes to run.

What javascript array methods runs at Linear time?

1. Shift
2. Unshift
3. Concat
4. Slice
5. Splice
6. Foreach
7. Map
8. Filter
9. Reduce

But shift and unshift does almost the same thing as push and pop, why are they not using constant time. Well shift and unshift affects the index of the array. shift removes the first element of an array while unshift add an element to the beginning of an array. This leads to extra work to change the index for all the items in the array. i just heard someone say loops. Yes you are right, that sounds like the work for a loop and anytime a single loop is involved, you are probably using a linear time because the length of the input matters. The higher the inputs, the more time it takes. Foreach, reduce, filter, splice, slice all makes use of loops under the hood.

Quadratic Time O(N^2) - When you code an algorithm and the time or space it takes to run is directly proportional to the square the size of the inputs used. i dont think it is clear enough so lets say you have a loop then you have another loop inside the first loop, this will lead to you having an algorithm with a quadratic time complexity.I always try to avoid using nested loops.

What javascript array methods runs at Quadratic time?

None ? well if you know one let me know in the comments

There are other types like O(Log N). I dont really know how to explain that well enough, maybe next time.

THANK YOU FOR READING