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

Big O Forum

View Course » View Exercise

2225 points
Picture
Submitted by
Lisa Ramos
almost 4 years ago

2.2 I'm confused

The instructions say to try to find N and C to show that f(n) = O(g(n)) even though f(n) is generally bigger than g(n). And then the hint says if you're having trouble finding the right N and C values, try doing a few examples on paper. If you can find some N and C values where f(N) < C*g(N), then you're probably on the right track. An excellent way to visualize this is to actually graph f(n), g(n), and C * g(n) on graph paper (notebook paper works too). Look for the point where C * g(n) = f(n). You want N to be beyond that point. There are many values of N and C that are acceptable. Your goal is to find a combination that works and try to understand why.

I've tried everything and it won't work and I'm still confused. Here's my code.

var f = function(n){
    return 5 * n + 2;
}; // f(n) = 5n+2

var g = function(n){
    return n;
};// g(n) = n


// Chose positive integers N and C to show f(n) = O(g(n))
var N = 5;
var C = function(n) {
    return n * 5.4;
};


// Checks 1000 values to ensure f(n) < C * g(n)
// In reality we would want to check all possible
//   values just to be sure, but that would take too long ;)

for (var n = N; n < N + 1000; n++){
    if(f(n) >= C * g(n)){ // f(n) should not be greater than C * g(n)
        console.log("n = " + n);
        console.log("f(n) = " + f(n));
        console.log("C*g(n) = " + (C * g(n)));
        console.log("Sorry, try choosing a larger C or N.");
        break;  // Exits the loop
    }else if(n >= N + 999)
        console.log("Good job, you found C and N!");
}

Can anyone please suggest any better solutions as to how this can be correctly done? Thanks.


0 votes

permalink

Never mind, I got it.

2225 points
Picture
Submitted by
Lisa Ramos
almost 4 years ago