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

Big O Forum

View Course » View Exercise

1187 points
Picture
Submitted by
Ross Studtman
almost 5 years ago

find n that will make 5n+2 = n? ...how's that possible?

"We're given f(n) = 5n+2 and g(n) = n. Try to find N and C to show that f(n) = O(g(n)) even though f(n) is usually bigger than g(n)."

N and C are positive numbers.

"We say that f(n) = O(g(n)) if we can find some positive numbers C and N where, when n >= N, f(n) < C * g(n)."

I'm looking for a positive number that is <= to n?

And, looking for another positive number that when multiplied by g(n) makes it bigger than f(n)?

5n+2 = O(n) ...if g(n) = n, then O(g(n)) evaluates to O(n).

Say n = 5 (just starting with a number from a hat).

5(5)+2 ...is 27. What function would O have to be to in order to return 27?

Algebra: x(5) = 27.....x = 27/5....x = 5.4.

O would have to be a function like this:

var O = function(n){
    return n * 5.4;
}

to satisfy this equation: 5(5)+2 = O(5)

Now I'm looking to fulfill this requirement: find some positive numbers C and N where, when n >= N, f(n) < C * g(n)

Since I chose 5 to be the value for n I know 4 is less than n. So N can be 4.

And then I'm looking for a value of C that will make f(n) < C * g(n) true. I know

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

returns 27. And g(n)' simply returnsn....so I can choose, say, **10** to be the value forC`....and 10 * g(n) = 50.

So I ask myself, is 27 < 50?

It is...and I've learned what?

I have no found values for N and C that work, and I've learned what?

I guess I'll have to scrounge the internet for a good tutorial on Big O that walks me through it like an infant because I'm not getting it. (that's not to sound defeatist, it's probably an accurate reflection of what I need).

PS: isn't f(n) always bigger than g(n) given the function f returns 5(n)+2 and function g returns just n? What's this "usually" talk (as long as we're dealing with positive numbers)?

...the only time g(n) is bigger than f(n) is when we "cheat" and boost g(n) side of the expression (isn't that a math no-no?).


1 vote

permalink

This seems to be a decent resource on Big O. It has some wonderful simplicity intertwined with stuff that goes zooming over my head.

I found this very quick guide to be helpful.

Taking cues from this resource I might explain Big O:

Big O is a way to express to people how long (in a worst case scenario, that's the "big" part) it will take to finish a project.

1...O(n) communicates to us that the time necessary to finish the project increases in direct proportion to the size of the project.

2... O(n^2) communicates to us that the time required to finish the project is no longer in direct proportion to the size of the project, instead as the project gets bigger the time to complete it is squared. So double the project size and the worst-case time to complete the project increases to 4. Make the project ten times bigger and the worst-case time to finish goes up by 100.

3...O(2^n) communicates to us that any increase in project size doubles the time to complete it. O(3^n) would triple the time for each increase in project size. This Big O is nasty for large projects.

4...O(log N) communicates....I don't have a handle on this one because I'm not familiar with logs. But it seems to say to us: the time to complete the project doesn't increase much even if the project size doubles or triples in size. Has to do with the ability of cutting projects in half (it's likely all of my words are on the 'shady' side but this is likely the shadiest thing I've said; but for someone who is just getting introduced, that's not a bad piece of knowledge to march with into the world of understanding binary searches.)**

1187 points
Picture
Submitted by
Ross Studtman
almost 5 years ago


1 vote

permalink

n= 5n + 2;  n= - 1/2  (it's not an integer, though).
Thanks for the links to Info on BigO.

 I changed the program  to see the calculated results of my tries for N and C - including if I guess correctly.

N: 2  C: 66  was a correct guess.

The resulting printout.
----------
N: 2  C: 66
f(n) = 12
C*g(n) = 132
Good job, you found C and N!
That's correct! Next Exercise: Linear Functions: O(n)
--------------------------------------

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 = 2;
var C = 66;
console.log("N: "+N+"  C: "+C);

// 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("n = " + n);
        console.log("f(n) = " + f(n));
        console.log("C*g(n) = " + (C * g(n)));
        console.log("Good job, you found C and N!");
        break;  // THIS BREAK IS IMPORTANT (if you don't want a long list of results.)
}

2198 points
561615eaafcf6921ce4288271566d49f?s=140&d=retro
Submitted by
kvkeller
almost 5 years ago

1 Comment

533b22568c1ccc6c0d00409e_910858883 Sofia Perwallius about 3 years ago

thanks a lot


0 votes

permalink

Here is a great link:
https://justin.abrah.ms/computer-science/how-to-calculate-big-o.html

As for this problem I think it's worded horribly and only serves to make you search the web for better explanations or guess wildly at solutions. Does N refer to O(g(n))?

541 points
521f8713f10c607a94000304_214739402
Submitted by
David Fox Powell
over 2 years ago