Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

big-O notation

tokoGtokoG Posts: 209Member
Hi

Does anybody know about this and how to "Find the big-O notation of the following functions"?

a) 20n^3 + 10 n lg n + 5

[b]Q1[/b]
What do you mean by, [red]find the big-O notation[/red]??
I was reading through my tutorial about big-O notation and what I understand is they use big-O notation to explain how complex the calculation (algorithm) can be with the huge numbers.
But... I can't relate to it to the above calculation. What (on earth!!) does it to do anything with it!!!?


Actually, this is NOT my assignment, so I have a solution here.
But I don't understand!

[b]It says...[/b]

[blue]
Since (n lg n) < n^2 < n^3,
[/blue]

[red][b]My comment[/b]
OK... so algorithm of (n lg n) grows slower than algorithm of n^2 and n^3, I understand that's why they explain above I think.
[/red]

[blue]
f(n) = [20n^3 + 10 n lg n + 5] < [20n^3 + 10n^3 + 5n^3]
[/blue]

[red][b]My question[/b]
OK... I understand why it's [b]left < right[/b] but, WHY we have to compare like this?
[/red]

[blue]
= (20 + 10 + 50)n^3
= 35n^3
= O(n^3)
[/blue]

[red][b]My question[/b]
Ummmmm..... :(
Then, why does it conclude like, 35n^3 therefore O(n^3)??? Dont understand this conclusion....
[/red]


If anybody understood what I wrote above, could you pls give me some advices??

Comments

  • IDKIDK Posts: 1,784Member
    [b][red]This message was edited by IDK at 2006-6-29 12:24:18[/red][/b][hr]

    : Hi
    :
    : Does anybody know about this and how to "Find the big-O notation of the following functions"?
    :
    : a) 20n^3 + 10 n lg n + 5
    :
    : [b]Q1[/b]
    : What do you mean by, [red]find the big-O notation[/red]??
    : I was reading through my tutorial about big-O notation and what I understand is they use big-O notation to explain how complex the calculation (algorithm) can be with the huge numbers.
    : But... I can't relate to it to the above calculation. What (on earth!!) does it to do anything with it!!!?
    :
    :
    : Actually, this is NOT my assignment, so I have a solution here.
    : But I don't understand!
    :
    : [b]It says...[/b]
    :
    : [blue]
    : Since (n lg n) < n^2 < n^3,
    : [/blue]
    :
    : [red][b]My comment[/b]
    : OK... so algorithm of (n lg n) grows slower than algorithm of n^2 and n^3, I understand that's why they explain above I think.
    : [/red]
    :
    : [blue]
    : f(n) = [20n^3 + 10 n lg n + 5] < [20n^3 + 10n^3 + 5n^3]
    : [/blue]
    :
    : [red][b]My question[/b]
    : OK... I understand why it's [b]left < right[/b] but, WHY we have to compare like this?
    : [/red]
    [green]
    Maybe they are saing that f(n) is [b]left[/b] in it's fastest case, and
    [b]right[/b] in it's slowest. Big O mesures the slowest case.
    [/green]

    :
    : [blue]
    : = (20 + 10 + 50)n^3
    : = 35n^3
    : = O(n^3)
    : [/blue]
    :
    : [red][b]My question[/b]
    : Ummmmm..... :(
    : Then, why does it conclude like, 35n^3 therefore O(n^3)??? Dont understand this conclusion....
    : [/red]

    [green]
    O(xn^3) = O(n^3)
    This is right...
    [/green]
    :
    :
    : If anybody understood what I wrote above, could you pls give me some advices??
    :
    [green]
    I don't really have a clue, but this is what I know of big O...

    EDIT: after a second thought, may be
    : a) 20n^3 + 10 n lg n + 5
    implies to the complexy of the function.

    The problem is then, what is the big O of 20n^3 + 10 n lg n + 5?
    O(20n^3 + 10 n lg n + 5) = O(n^3)

    I may be all wrong...
    [/green]
  • tokoGtokoG Posts: 209Member
    : [b][red]This message was edited by IDK at 2006-6-29 12:24:18[/red][/b][hr]
    :

    : : a) 20n^3 + 10 n lg n + 5

    : :
    : : [b]It says...[/b]
    : :
    : : [blue]
    : : Since (n lg n) < n^2 < n^3,
    : : [/blue]
    : :
    : : [red][b]My comment[/b]
    : : OK... so algorithm of (n lg n) grows slower than algorithm of n^2 and n^3, I understand that's why they explain above I think.
    : : [/red]
    ------------------------------------------------------------
    : : [blue]
    : : f(n) = [20n^3 + 10 n lg n + 5] < [20n^3 + 10n^3 + 5n^3]
    : : [/blue]
    : :
    : : [red][b]My question[/b]
    : : OK... I understand why it's [b]left < right[/b] but, WHY we have to compare like this?
    : : [/red]
    : [green]
    : Maybe they are saing that f(n) is [b]left[/b] in it's fastest case, and
    : [b]right[/b] in it's slowest. Big O mesures the slowest case.
    : [/green]
    :

    [red][b]tokoG[/b]
    I see... The Big O measures the SLOWEST CASE of given calculations.
    I have other examples and comparing them now and yes, I think they started making sense to me..
    [/red]
    ----------------------------------------------------------
    : :
    : : [blue]
    : : = (20 + 10 + 50)n^3
    : : = 35n^3
    : : = O(n^3)
    : : [/blue]
    : :
    : : [red][b]My question[/b]
    : : Ummmmm..... :(
    : : Then, why does it conclude like, 35n^3 therefore O(n^3)??? Dont understand this conclusion....
    : : [/red]
    :
    : [green]
    : O(xn^3) = O(n^3)
    : This is right...
    : [/green]
    : :
    [red][b]tokoG[/b]
    Right, because big O treats the ridiculously huge numbers so multifying ay the constant doesnt give much change. I think that's what it means?
    [/red]
    -----------------------------------------------------------------
    : : If anybody understood what I wrote above, could you pls give me some advices??
    : :
    : [green]
    : I don't really have a clue, but this is what I know of big O...
    :
    : EDIT: after a second thought, may be
    : : a) 20n^3 + 10 n lg n + 5
    : implies to the complexy of the function.
    :
    : The problem is then, what is the big O of 20n^3 + 10 n lg n + 5?
    : O(20n^3 + 10 n lg n + 5) = O(n^3)
    :
    : I may be all wrong...
    : [/green]
    :

    [red][b]tokoG[/b]
    Or you are maybe all correct....
    I think at least I understand what big-O notation is now.. phew.
    Now I have to sort these questions follows;
    [/red]




    =============================================
    [italic]Re-express the following functions of algorithm exmplexity using big-O notation. Note that the expression f(n) = O(g(n)) implies that f(n) <= cg(n) for all n >= n0[/italic]

    [b](i) 20000n + 20[/b]

    [blue]
    I think... this is,

    [20000n + 20] < [20000n + 20n]
    = (20000 + 20)n
    = (20020)n
    = O(n)

    [/blue]

    [b](ii)n^3 + 30 n lg n[/b]

    [blue]
    I think this is...

    [n^3 + 20 n lg n] < [n^3 + 30n^3] .... as log makes it smaller
    = (1 + 30)n^3
    = (31)n^3
    = O(n3)
    [/blue]

    [b](iii) 2[/b]

    [blue]
    Well,,, this is a constant and independant of n, f(n) = 2 = O(1)
    [/blue]

    I guess this is alright... not sure but it should be..?

    Thanks IDK!!
  • IDKIDK Posts: 1,784Member
    : : [b][red]This message was edited by IDK at 2006-6-29 12:24:18[/red][/b][hr]
    : :
    :
    : : : a) 20n^3 + 10 n lg n + 5
    :
    : : :
    : : : [b]It says...[/b]
    : : :
    : : : [blue]
    : : : Since (n lg n) < n^2 < n^3,
    : : : [/blue]
    : : :
    : : : [red][b]My comment[/b]
    : : : OK... so algorithm of (n lg n) grows slower than algorithm of n^2 and n^3, I understand that's why they explain above I think.
    : : : [/red]
    : ------------------------------------------------------------
    : : : [blue]
    : : : f(n) = [20n^3 + 10 n lg n + 5] < [20n^3 + 10n^3 + 5n^3]
    : : : [/blue]
    : : :
    : : : [red][b]My question[/b]
    : : : OK... I understand why it's [b]left < right[/b] but, WHY we have to compare like this?
    : : : [/red]
    : : [green]
    : : Maybe they are saing that f(n) is [b]left[/b] in it's fastest case, and
    : : [b]right[/b] in it's slowest. Big O mesures the slowest case.
    : : [/green]
    : :
    :
    : [red][b]tokoG[/b]
    : I see... The Big O measures the SLOWEST CASE of given calculations.
    : I have other examples and comparing them now and yes, I think they started making sense to me..
    : [/red]
    : ----------------------------------------------------------
    : : :
    : : : [blue]
    : : : = (20 + 10 + 50)n^3
    : : : = 35n^3
    : : : = O(n^3)
    : : : [/blue]
    : : :
    : : : [red][b]My question[/b]
    : : : Ummmmm..... :(
    : : : Then, why does it conclude like, 35n^3 therefore O(n^3)??? Dont understand this conclusion....
    : : : [/red]
    : :
    : : [green]
    : : O(xn^3) = O(n^3)
    : : This is right...
    : : [/green]
    : : :
    : [red][b]tokoG[/b]
    : Right, because big O treats the ridiculously huge numbers so multifying ay the constant doesnt give much change. I think that's what it means?
    : [/red]
    : -----------------------------------------------------------------
    : : : If anybody understood what I wrote above, could you pls give me some advices??
    : : :
    : : [green]
    : : I don't really have a clue, but this is what I know of big O...
    : :
    : : EDIT: after a second thought, may be
    : : : a) 20n^3 + 10 n lg n + 5
    : : implies to the complexy of the function.
    : :
    : : The problem is then, what is the big O of 20n^3 + 10 n lg n + 5?
    : : O(20n^3 + 10 n lg n + 5) = O(n^3)
    : :
    : : I may be all wrong...
    : : [/green]
    : :
    :
    : [red][b]tokoG[/b]
    : Or you are maybe all correct....
    : I think at least I understand what big-O notation is now.. phew.
    : Now I have to sort these questions follows;
    : [/red]
    :
    :
    :
    :
    : =============================================
    : [italic]Re-express the following functions of algorithm exmplexity using big-O notation. Note that the expression f(n) = O(g(n)) implies that f(n) <= cg(n) for all n >= n0[/italic]
    :
    : [b](i) 20000n + 20[/b]
    :
    : [blue]
    : I think... this is,
    :
    : [20000n + 20] < [20000n + 20n]
    : = (20000 + 20)n
    : = (20020)n
    : = O(n)
    :
    : [/blue]
    :
    : [b](ii)n^3 + 30 n lg n[/b]
    :
    : [blue]
    : I think this is...
    :
    : [n^3 + 20 n lg n] < [n^3 + 30n^3] .... as log makes it smaller
    : = (1 + 30)n^3
    : = (31)n^3
    : = O(n3)
    : [/blue]
    :
    : [b](iii) 2[/b]
    :
    : [blue]
    : Well,,, this is a constant and independant of n, f(n) = 2 = O(1)
    : [/blue]
    :
    : I guess this is alright... not sure but it should be..?
    :
    : Thanks IDK!!
    :
    NP!

    Everything seems right to me...


    Why do one have to calculate it?
    It's only to take the biggest faktor and remove the constant.

    : [b](ii)n^3 + 30 n lg n[/b]
    : [n^3 + 20 n lg n] < [n^3 + 30n^3] .... as log makes it smaller
    : = (1 + 30)n^3
    : = (31)n^3
    : = O(n3)
    Insted of doing this calculation, ask yourself:
    what is the biggest power of n?

    In the above it is n^3, wich gives O(n^3).
  • Gregry2Gregry2 Posts: 607Member
    : : : [b][red]This message was edited by IDK at 2006-6-29 12:24:18[/red][/b][hr]
    : : :
    : :
    : : : : a) 20n^3 + 10 n lg n + 5
    : :
    : : : :
    : : : : [b]It says...[/b]
    : : : :
    : : : : [blue]
    : : : : Since (n lg n) < n^2 < n^3,
    : : : : [/blue]
    : : : :
    : : : : [red][b]My comment[/b]
    : : : : OK... so algorithm of (n lg n) grows slower than algorithm of n^2 and n^3, I understand that's why they explain above I think.
    : : : : [/red]
    : : ------------------------------------------------------------
    : : : : [blue]
    : : : : f(n) = [20n^3 + 10 n lg n + 5] < [20n^3 + 10n^3 + 5n^3]
    : : : : [/blue]
    : : : :
    : : : : [red][b]My question[/b]
    : : : : OK... I understand why it's [b]left < right[/b] but, WHY we have to compare like this?
    : : : : [/red]
    : : : [green]
    : : : Maybe they are saing that f(n) is [b]left[/b] in it's fastest case, and
    : : : [b]right[/b] in it's slowest. Big O mesures the slowest case.
    : : : [/green]
    : : :
    : :
    : : [red][b]tokoG[/b]
    : : I see... The Big O measures the SLOWEST CASE of given calculations.
    : : I have other examples and comparing them now and yes, I think they started making sense to me..
    : : [/red]
    : : ----------------------------------------------------------
    : : : :
    : : : : [blue]
    : : : : = (20 + 10 + 50)n^3
    : : : : = 35n^3
    : : : : = O(n^3)
    : : : : [/blue]
    : : : :
    : : : : [red][b]My question[/b]
    : : : : Ummmmm..... :(
    : : : : Then, why does it conclude like, 35n^3 therefore O(n^3)??? Dont understand this conclusion....
    : : : : [/red]
    : : :
    : : : [green]
    : : : O(xn^3) = O(n^3)
    : : : This is right...
    : : : [/green]
    : : : :
    : : [red][b]tokoG[/b]
    : : Right, because big O treats the ridiculously huge numbers so multifying ay the constant doesnt give much change. I think that's what it means?
    : : [/red]
    : : -----------------------------------------------------------------
    : : : : If anybody understood what I wrote above, could you pls give me some advices??
    : : : :
    : : : [green]
    : : : I don't really have a clue, but this is what I know of big O...
    : : :
    : : : EDIT: after a second thought, may be
    : : : : a) 20n^3 + 10 n lg n + 5
    : : : implies to the complexy of the function.
    : : :
    : : : The problem is then, what is the big O of 20n^3 + 10 n lg n + 5?
    : : : O(20n^3 + 10 n lg n + 5) = O(n^3)
    : : :
    : : : I may be all wrong...
    : : : [/green]
    : : :
    : :
    : : [red][b]tokoG[/b]
    : : Or you are maybe all correct....
    : : I think at least I understand what big-O notation is now.. phew.
    : : Now I have to sort these questions follows;
    : : [/red]
    : :
    : :
    : :
    : :
    : : =============================================
    : : [italic]Re-express the following functions of algorithm exmplexity using big-O notation. Note that the expression f(n) = O(g(n)) implies that f(n) <= cg(n) for all n >= n0[/italic]
    : :
    : : [b](i) 20000n + 20[/b]
    : :
    : : [blue]
    : : I think... this is,
    : :
    : : [20000n + 20] < [20000n + 20n]
    : : = (20000 + 20)n
    : : = (20020)n
    : : = O(n)
    : :
    : : [/blue]
    : :
    : : [b](ii)n^3 + 30 n lg n[/b]
    : :
    : : [blue]
    : : I think this is...
    : :
    : : [n^3 + 20 n lg n] < [n^3 + 30n^3] .... as log makes it smaller
    : : = (1 + 30)n^3
    : : = (31)n^3
    : : = O(n3)
    : : [/blue]
    : :
    : : [b](iii) 2[/b]
    : :
    : : [blue]
    : : Well,,, this is a constant and independant of n, f(n) = 2 = O(1)
    : : [/blue]
    : :
    : : I guess this is alright... not sure but it should be..?
    : :
    : : Thanks IDK!!
    : :
    : NP!
    :
    : Everything seems right to me...
    :
    :
    : Why do one have to calculate it?
    : It's only to take the biggest faktor and remove the constant.
    :
    : : [b](ii)n^3 + 30 n lg n[/b]
    : : [n^3 + 20 n lg n] < [n^3 + 30n^3] .... as log makes it smaller
    : : = (1 + 30)n^3
    : : = (31)n^3
    : : = O(n3)
    : Insted of doing this calculation, ask yourself:
    : what is the biggest power of n?
    :
    : In the above it is n^3, wich gives O(n^3).
    :
    Unrelated:

    Hey tokoG, I noticed you really format your posts well...if you enjoy it, you might like HTML, it the language used for making web pages. Its alot like the "stylecodes" on this site.

    HTML isn't so program-ish, I mean its not so mathematical and stuff, you might like it. You arrange text and wrap it in tags, just like the [leftbr]red[rightbr][red]blah blah[/red][leftbr]/red[rightbr], it can get more complicated, but ou knowledge of C/C++ will help you with those parts (the scripts)

    another thing. Your username, I think I know the toko part, but the what is the `G' for? girl?

    just wondering.
    {2}rIng

  • tokoGtokoG Posts: 209Member

    : NP!
    :
    : Everything seems right to me...
    :
    :
    : Why do one have to calculate it?
    : It's only to take the biggest faktor and remove the constant.
    :
    : : [b](ii)n^3 + 30 n lg n[/b]
    : : [n^3 + 20 n lg n] < [n^3 + 30n^3] .... as log makes it smaller
    : : = (1 + 30)n^3
    : : = (31)n^3
    : : = O(n3)
    : Insted of doing this calculation, ask yourself:
    : what is the biggest power of n?
    :
    : In the above it is n^3, wich gives O(n^3).
    :



    Yeah... it's just that the school project.
    I just need to SHOW step by step Big-O notation calculation.
    I think they are testing us whether we really understood this notation.

    :)
  • tokoGtokoG Posts: 209Member

    : Hey tokoG, I noticed you really format your posts well...if you enjoy it, you might like HTML, it the language used for making web pages. Its alot like the "stylecodes" on this site.
    :
    : HTML isn't so program-ish, I mean its not so mathematical and stuff, you might like it. You arrange text and wrap it in tags, just like the [leftbr]red[rightbr][red]blah blah[/red][leftbr]/red[rightbr], it can get more complicated, but ou knowledge of C/C++ will help you with those parts (the scripts)
    :
    : another thing. Your username, I think I know the toko part, but the what is the `G' for? girl?
    :
    : just wondering.
    : {2}rIng
    :
    :



    Hah ha hah hah... yes, I organise my post quite well as you said... I like visual explanation and if it's not visually organised, I can't understand things in general. I am lefty and my right side of the brain proberbly works better than my left side. = means I am not logical person at all!

    I thought about HTML coding and I found some tutorial web site. But I dont do blog (at the moment) and I dont have my own web site and have no plan to have it near future at the moment. I think what we do on the thread on this message board is also HTML coding is it??

    Yes, toko is my name and G stands for GRRRL ... or girl. ;)
    My web nick name as well as freelancing nick name for illustrations.
    You guessed right!


  • Gregry2Gregry2 Posts: 607Member
    [b][red]This message was edited by Gregry2 at 2006-7-3 6:7:32[/red][/b][hr]
    :
    : Hah ha hah hah... yes, I organise my post quite well as you said... I like visual explanation and if it's not visually organised, I can't understand things in general. I am lefty and my right side of the brain proberbly works better than my left side. = means I am not logical person at all!
    :
    : I thought about HTML coding and I found some tutorial web site. But I dont do blog (at the moment) and I dont have my own web site and have no plan to have it near future at the moment. I think what we do on the thread on this message board is also HTML coding is it??
    :

    [green]Not really...the "stylecodes" are probably just read by the scripts that generate these pages, then the scripts generate corresponding html. I dont noe, htmling is fun, even if you just save it on ur computer and look at it, I cant afford a domain on the web, unless I go and get a 'free' one with all those spyware ads, and I dont do blogs either...but its nice to know, for me.[/green]

    :
    : Yes, toko is my name and G stands for GRRRL ... or girl. ;)
    : My web nick name as well as freelancing nick name for illustrations.
    : You guessed right!
    :
    [green]
    Oh, its ur name...i didnt noe that...lol, i thought it only meant forever or endless and u just added it...but its ur name also, is it really 'ever', or its not toko, but touko or tooko...or tokou...romaji spellings vary so much...

    im studying japanese a little...thats all :)
    {2}rIng

    [/green]
  • IDKIDK Posts: 1,784Member

    : [green]Not really...the "stylecodes" are probably just read by the scripts that generate these pages, then the scripts generate corresponding html. I dont noe, htmling is fun, even if you just save it on ur computer and look at it, I cant afford a domain on the web, unless I go and get a 'free' one with all those spyware ads, and I dont do blogs either...but its nice to know, for me.[/green]

    I got a .tk domain. It's free, there isn't any spam or mercendize...
    www.ns-dos.tk
    Try it out.

    To everyone...
    I'm on a vacation for 3 weeks, that's why I'm not writing very much things in the forums. I found an internet kafe here, and it was very cheep (1 pound for an hour).

Sign In or Register to comment.