CODEWITHSUNDEEP
javascripttime-complexitybig-ocomputer-science
colbisaurusrex
colbisaurusrex

Reputation: 105

What is the time complexity of this for loop nested in a while loop?

I am trying to optimize a function. I believe this nested for loop is quadratic, but I'm not positive. I have recreated the function below

const bucket = [["e","f"],[],["j"],[],["p","q"]]
let totalLettersIWantBack = 4;

//I'm starting at the end of the bucket
function produceLetterArray(bucket, limit){
  let result = [];
  let countOfLettersAccumulated = 0;
  let i = bucket.length - 1;
    while(i > 0){
      if(bucket[i].length > 0){
        bucket[i].forEach( (letter) =>{
        if(countOfLettersAccumulated === totalLettersIWantBack){
          return;
        }
        result.push(letter);
       countOfLettersAccumulated++;
        })
      }
      i--;
    }
  return result;
}

console.log(produceLetterArray(bucket, totalLettersIWantBack));

Upvotes: 2

Views: 1876

Answers (4)

Rudolf Manusachi
Rudolf Manusachi

Reputation: 2346

I like @axiom's explanation of complexity analyze.

Just would like to add possible optimized solution.

UPD .push (O(1)) is faster that .concat (O(n^2))

also here is test Array push vs. concat

const bucket = [["e","f"],[],["j", 'm', 'b'],[],["p","q"]]
let totalLettersIWantBack = 4;

//I'm starting at the end of the bucket
function produceLetterArray(bucket, limit){
  let result = [];

  for(let i = bucket.length-1; i > 0 && result.length < totalLettersIWantBack; i--){
    //previous version
    //result = result.concat(bucket[i].slice(0, totalLettersIWantBack-result.length));
    
    //faster version of merging array
    Array.prototype.push.apply(result, bucket[i].slice(0, totalLettersIWantBack-result.length));
  }
  return result;
}

console.log(produceLetterArray(bucket, totalLettersIWantBack));

Upvotes: 0

Aman
Aman

Reputation: 8995

Here is a trick for such questions. For the code whose complexity you want to analyze, just write the time that it would take to execute each statement in the worst case assuming no other statement exists. Note the comments begining with #operations worst case:

For the given code:

while(i > 0){ //#operations worst case: bucket.length
  if(bucket[i].length > 0){ //#operations worst case:: 1
    bucket[i].forEach( (letter) =>{  //#operations worst case: max(len(bucket[i])) for all i
    if(countOfLettersAccumulated === totalLettersIWantBack){ //#operations worst case:1
      return;
    }
    result.push(letter); //#operations worst case:1
   countOfLettersAccumulated++; //#operations worst case:1
    })
  }
  i--; ////#operations worst case:: 1
}

We can now multiply all the worst case times (since they all can be achieved in the worst case, you can always set totalLettersIWantBack = 10^9) to get the O complexity of the snippet:

Complexity = O(bucket.length * 1 * max(len(bucket[i])) * 1 * 1 * 1 * 1)

= O(bucket.length * max(len(bucket[i]))

If the length of each of the bucket[i] was a constant, K, then your complexity reduces to: O(K * bucket.length ) = O(bucket.length)

Note that the complexity of the push operation may not remain constant as the number of elements grow (ultimately, the runtime will need to allocate space for the added elements, and all the existing elements may have to be moved).

Upvotes: 4

Krupip
Krupip

Reputation: 4882

Whether or not this is quadratic depends on what you consider N and how bucket is organized. If N is the total number of letters, then the runtime is bound by either the number of bins in your bucket, if that is larger than N, or it is bound by the number of letters in the bucket, if N is larger. In either case, the search time increases linearly with the larger bound, if one would dominate the other the time complexity is O(N). This is effectively a linear search with "turns" in it, scrunching a linear search and spacing it out does not change the time complexity. The existence of multiple loops in a piece of code does not alone make it non linear. Take the linear search example again. We search a list until we've found the largest element. 

//12 elements
var array = [0,1,2,3,4,5,6,7,8,9,10,11];
var rows = 3;
var cols = 4;

var largest = -1;

for(var i = 0; i < rows; ++i){

    for(var j = 0; j < cols; ++j){
        var checked = array[(i * cols) + j];
        if (checked > largest){
            largest = checked;
        }      
    } 
}
console.log("found largest number (eleven): " + largest.toString());

Despite this using two loops instead of one, the runtime complexity is still O(N) where N is the number of elements in the input. Scrunching this down so each index is actually an array to multiple elements, or separating relevant elements by empty bins doesn't change the fact the runtime complexity is bound linearly.

Upvotes: 1

Alex Ehlert
Alex Ehlert

Reputation: 474

This is technically linear with n being the number of elements total in your matrix. This is because the exit condition is the length of bucket and for each array in bucket you check if countOfLettersAccumulated is equal to totalLettersIWantBack. Continually looking at values.

It gets a lot more complicated if you are looking for an answer matching the dimensions of your matrix because it looks like the dimensions of bucket are not fixed.

You can turn this bit of code into constant by adding an additional check outside the bucket foreach which if countOfLettersAccumulated is equal to totalLettersIWantBack then you do a break.

Upvotes: 0

Related Questions