This forum is now read-only. Please use our new forums at discuss.codecademy.com.

Big O Forum

View Course

500 points
Picture
Submitted by
Rafael Espinoza Kim
over 4 years ago

Figuring out the logic behind 2.1 *spoiler

So, I think I have it figured out...but please feel free to comment on my logic:

This exercise basically returns an array containing all the possible combinations using 1 and 0 in a string of length (n).

The answer is O(2^n) because the amount of possible combinations is

2^n. That is why you get 4 elements (2^2) with 2 digits, 8 elements (2^3) with 3 digits and so on. Therefore the function is exponentially proportionate to the amount of digits.

How the code works:

var binary = function(n){
var helper = function(i, s){
    // If there are no characters left to print, then stop printing
//THIS MEANS THAT AN ARRAY WITH VALUE S WILL BE CREATED WHEN i = 0 OR LOWER.
    if(i < 1) return [s];

    // array1.concat(array2) is a new array containing the elements of array1 followed by those of array2
return helper(i-1, "1"+s).concat(helper(i-1, "0"+s));

// Forget about all the concats below, it was just a way to follow logic.  Remember
//concat "attaches" two strings. By putting "1" + s, basically we are saying that "1" is a string, not a number.  This way it will attach and not add.

//`with binary (3)
        //helper(2,1).concat(helper(2,0))

        //helper(1,11).concat(helper(1,01).concat(helper(1,10),concat(helper(1,00))))
        //helper()

        //helper((0,111).concat(0,011)).concat(0,101)(0,001)......etc,etc
// Since i < 1 here, we start printing, the first helper will make [s] = 111, second one will make [s] = [111] .concat[011] which is [111,011] this logic follows until giving the ending array: [ "111", "011", "101", "001", "110", "010", "100", "000"]

    return helper(n, "");
}

console.log(binary(0));
console.log("O(2^n)")

2 votes

permalink

good stuff thanks

1285 points
50b6105320fce39ed8001e12_222544037
Submitted by
Devin Ryan
over 4 years ago

2 Comments

81d71b58bbfeb83e86e831ffede7269f?s=140&d=retro Hun about 4 years ago

seconded!

533b22568c1ccc6c0d00409e_910858883 Sofia Perwallius about 3 years ago

Thanks