CODEWITHSUNDEEP
javascriptalgorithm
ChromeBrowser
ChromeBrowser

Reputation: 219

O(1) vs O(n) in Space Complexity

O(1)
function sum(arr) {
   let total = 0;
   for (let i = 0; i < arr.length; i++) {
        total += arr[i]; 
    }
    return total;
}

function double(arr) {
   let newArr = [];
   for (let i=0; i<arr.length; i++) {
       newArr.push(2 * arr[i]);
       }
   return newArr;
}

So i studying algorithm using javascript. The first one I think is O(1) because it has constant space. The reason why it has constant space is because number data types are constant space in javascript. The second one makes a new array which is generally O(n) which makes its space complexity O(n). Am i understanding it right?

Upvotes: 1

Views: 947

Answers (1)

CertainPerformance
CertainPerformance

Reputation: 370689

You're mostly right, though it's not just that the second code makes a new array - you have to look at what the array contains. Here, on every iteration, a new number is pushed to the array. So if you have N items in the arr argument, you'll have N numbers in the newArr as well.

One array * N numbers means O(n) space used.

If the arr was changed to contain something else more complex, such as additional sub-arrays, the space complexity could be larger.

Upvotes: 3

Related Questions