## C and C++

Moderators: None (Apply to moderate this forum)
Number of posts: 94611

This Forum Only

big-O notation Posted by tokoG on 29 Jun 2006 at 7:35 AM
Hi

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

Q1
What do you mean by, find the big-O notation??
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!

It says...

Since (n lg n) < n^2 < n^3,

My comment
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.

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

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

= (20 + 10 + 50)n^3
= 35n^3
= O(n^3)

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

If anybody understood what I wrote above, could you pls give me some advices??
Re: big-O notation Posted by IDK on 29 Jun 2006 at 11:45 AM
This message was edited by IDK at 2006-6-29 12:24:18

: 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
:
: Q1
: What do you mean by, find the big-O notation??
: 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!
:
: It says...
:
:
: Since (n lg n) < n^2 < n^3,
:

:
: My comment
: 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.
:

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

:
: My question
: OK... I understand why it's left < right but, WHY we have to compare like this?
:

Maybe they are saing that f(n) is left in it's fastest case, and
right in it's slowest. Big O mesures the slowest case.

:
:
: = (20 + 10 + 50)n^3
: = 35n^3
: = O(n^3)
:

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

O(xn^3) = O(n^3)
This is right...

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

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...

Re: big-O notation Posted by tokoG on 29 Jun 2006 at 8:50 PM
: This message was edited by IDK at 2006-6-29 12:24:18

:

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

: :
: : It says...
: :
: :
: : Since (n lg n) < n^2 < n^3,
: :

: :
: : My comment
: : 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.
: :

------------------------------------------------------------
: :
: : f(n) = [20n^3 + 10 n lg n + 5] < [20n^3 + 10n^3 + 5n^3]
: :

: :
: : My question
: : OK... I understand why it's left < right but, WHY we have to compare like this?
: :

:
: Maybe they are saing that f(n) is left in it's fastest case, and
: right in it's slowest. Big O mesures the slowest case.
:

:

tokoG
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..

----------------------------------------------------------
: :
: :
: : = (20 + 10 + 50)n^3
: : = 35n^3
: : = O(n^3)
: :

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

:
:
: O(xn^3) = O(n^3)
: This is right...
:

: :
tokoG
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?

-----------------------------------------------------------------
: : If anybody understood what I wrote above, could you pls give me some advices??
: :
:
: 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...
:

:

tokoG
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;

=============================================
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

(i) 20000n + 20

I think... this is,

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

(ii)n^3 + 30 n lg n

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)

(iii) 2

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

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

Thanks IDK!!
Re: big-O notation Posted by IDK on 30 Jun 2006 at 2:57 AM
: : This message was edited by IDK at 2006-6-29 12:24:18

: :
:
: : : a) 20n^3 + 10 n lg n + 5
:
: : :
: : : It says...
: : :
: : :
: : : Since (n lg n) < n^2 < n^3,
: : :

: : :
: : : My comment
: : : 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.
: : :

: ------------------------------------------------------------
: : :
: : : f(n) = [20n^3 + 10 n lg n + 5] < [20n^3 + 10n^3 + 5n^3]
: : :

: : :
: : : My question
: : : OK... I understand why it's left < right but, WHY we have to compare like this?
: : :

: :
: : Maybe they are saing that f(n) is left in it's fastest case, and
: : right in it's slowest. Big O mesures the slowest case.
: :

: :
:
: tokoG
: 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..
:

: ----------------------------------------------------------
: : :
: : :
: : : = (20 + 10 + 50)n^3
: : : = 35n^3
: : : = O(n^3)
: : :

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

: :
: :
: : O(xn^3) = O(n^3)
: : This is right...
: :

: : :
: tokoG
: 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?
:

: -----------------------------------------------------------------
: : : If anybody understood what I wrote above, could you pls give me some advices??
: : :
: :
: : 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...
: :

: :
:
: tokoG
: 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;
:

:
:
:
:
: =============================================
: 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
:
: (i) 20000n + 20
:
:
: I think... this is,
:
: [20000n + 20] < [20000n + 20n]
: = (20000 + 20)n
: = (20020)n
: = O(n)
:
:

:
: (ii)n^3 + 30 n lg n
:
:
: 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)
:

:
: (iii) 2
:
:
: Well,,, this is a constant and independant of n, f(n) = 2 = O(1)
:

:
: 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.

: (ii)n^3 + 30 n lg n
: [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).
Re: big-O notation Posted by Gregry2 on 30 Jun 2006 at 5:36 AM
: : : This message was edited by IDK at 2006-6-29 12:24:18

: : :
: :
: : : : a) 20n^3 + 10 n lg n + 5
: :
: : : :
: : : : It says...
: : : :
: : : :
: : : : Since (n lg n) < n^2 < n^3,
: : : :

: : : :
: : : : My comment
: : : : 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.
: : : :

: : ------------------------------------------------------------
: : : :
: : : : f(n) = [20n^3 + 10 n lg n + 5] < [20n^3 + 10n^3 + 5n^3]
: : : :

: : : :
: : : : My question
: : : : OK... I understand why it's left < right but, WHY we have to compare like this?
: : : :

: : :
: : : Maybe they are saing that f(n) is left in it's fastest case, and
: : : right in it's slowest. Big O mesures the slowest case.
: : :

: : :
: :
: : tokoG
: : 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..
: :

: : ----------------------------------------------------------
: : : :
: : : :
: : : : = (20 + 10 + 50)n^3
: : : : = 35n^3
: : : : = O(n^3)
: : : :

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

: : :
: : :
: : : O(xn^3) = O(n^3)
: : : This is right...
: : :

: : : :
: : tokoG
: : 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?
: :

: : -----------------------------------------------------------------
: : : : If anybody understood what I wrote above, could you pls give me some advices??
: : : :
: : :
: : : 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...
: : :

: : :
: :
: : tokoG
: : 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;
: :

: :
: :
: :
: :
: : =============================================
: : 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
: :
: : (i) 20000n + 20
: :
: :
: : I think... this is,
: :
: : [20000n + 20] < [20000n + 20n]
: : = (20000 + 20)n
: : = (20020)n
: : = O(n)
: :
: :

: :
: : (ii)n^3 + 30 n lg n
: :
: :
: : 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)
: :

: :
: : (iii) 2
: :
: :
: : Well,,, this is a constant and independant of n, f(n) = 2 = O(1)
: :

: :
: : 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.
:
: : (ii)n^3 + 30 n lg n
: : [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 [red]blah blah[/red], 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

Re: big-O notation Posted by tokoG on 2 Jul 2006 at 9:53 PM

: 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 [red]blah blah[/red], 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!

Re: big-O notation Posted by Gregry2 on 3 Jul 2006 at 6:00 AM
This message was edited by Gregry2 at 2006-7-3 6:7:32

:
: 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??
:

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.

:
: 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!
:

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

Re: big-O notation Posted by IDK on 5 Jul 2006 at 12:56 PM

: 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.

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).

Re: big-O notation Posted by tokoG on 2 Jul 2006 at 9:48 PM

: 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.
:
: : (ii)n^3 + 30 n lg n
: : [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.

:)

## Recent Jobs

Official Programmer's Heaven Blogs
Web Hosting | Browser and Social Games | Gadgets

Popular resources on Programmersheaven.com
Assembly | Basic | C | C# | C++ | Delphi | Flash | Java | JavaScript | Pascal | Perl | PHP | Python | Ruby | Visual Basic