array-methods-Big-O.js

/* Identify the time complexity of each of these functions with a 1 sentence justification for your answer. Assume arr is an array of length n.

arr.push()
Time complexity: O(1) Space complexity: O(1) Justification: .push() mutates the input array inplace there by not using the array's length property to identify a valid length and placing the new element at that position, it also does'nt create an new array

push on MDN

arr.pop()
Time complexity: O(1) Space complexity: O(1) Justification: .pop() works just like push()

pop on MDN

arr.shift()
Time complexity: O(n) Space complexity: O(1) Justification: .shift() works like pop, but reverse position, 

shift on MDN

arr.unshift()
Time complexity: O(n) Space complexity: O(1) Justification: .unshift() works like shift()

unshift on MDN

arr.splice()
Time complexity: O(n) Space complexity: O(n) Justification: works in place, doesn't create new items, and uses the object length to find the index at constant time and space

splice on MDN

arr.slice()
Time complexity: O(n) Space complexity: O(n) Justification: creates a new array, works on linear time because the item to splice may be anywhere

slice on MDN

arr.indexOf()
Time complexity: O(n) Space complexity: O(1) Justification: worst case, the item is not found, it has to go throught the whole array to find that out, linear time and constant space complexities

indexOf on MDN

arr.map()
Time complexity: O(n) Space complexity: O(n) Justification: creates an new array, and does work on each element of the input array, linear space and time

map on MDN

arr.filter()
Time complexity: O(n) Space complexity: O(n) Justification: creates a new array, and does work on each element of the input array. Linear space and time

filter on MDN

arr.reduce()
Time complexity: O(n) Space complexity: O(1) Justification: it does work on each element in the array, thereby working in linear time and constant space complexities

reduce on MDN

arr.reverse()
Time complexity: O(n) Space complexity: O(1) Justification: it reverses an array in place but depends the length of the array, linear time and constant space complexities

reverse on MDN

[...arr]
Time complexity: O(n) Space complexity: O(n) Justification: depends on the amount of input and creates new array, linear space and time

spread on MDN

*/

/**
BING AI's thoughts

Your comments on time and space complexities are mostly correct, but there are a few inaccuracies. Here's the corrected version:

1. `arr.push()`: Time complexity is **O(1)** because adding an element to the end of an array is a constant time operation. Space complexity is **O(1)** because no additional space is used.

2. `arr.pop()`: Time complexity is **O(1)** because removing an element from the end of an array is a constant time operation. Space complexity is **O(1)**.

3. `arr.shift()`: Time complexity is **O(n)** because all elements have to be re-indexed after removing the first element. Space complexity is **O(1)**.

4. `arr.unshift()`: Time complexity is **O(n)** because all elements have to be re-indexed after adding an element at the beginning. Space complexity is **O(1)**.

5. `arr.splice()`: Time complexity can be up to **O(n)** because it may require shifting elements over by one. Space complexity is **O(n)** because it returns a new array containing the deleted elements.

6. `arr.slice()`: Time complexity is **O(n)** because it creates a new array and copies over n elements. Space complexity is **O(n)** because it returns a new array.

7. `arr.indexOf()`: Time complexity is **O(n)** because in the worst case, you might have to look at every element in the list. Space complexity is **O(1)**.

8. `arr.map()`, `arr.filter()`: Both have time and space complexities of **O(n)** because they create a new array and perform an operation for each element in the original array.

9. `arr.reduce()`: Time complexity is **O(n)** because it processes each element in the array once, and space complexity is **O(1)** because it only returns a single output value.

10. `arr.reverse()`: Time complexity is **O(n)** because it has to swap n/2 elements, and space complexity is **O(1)** because it reverses the array in place.

11. `[...arr]`: Time complexity is **O(n)** because it iterates over the array to create a copy, and space complexity is also **O(n)** because it creates a new array.
*/