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

- 141.5K All Categories
- 104.7K Programming Languages
- 6.4K Assembler Developer
- 1.9K Basic
- 39.8K C and C++
- 4.3K C#
- 7.9K Delphi and Kylix
- 4 Haskell
- 9.6K Java
- 4.1K Pascal
- 1.3K Perl
- 2K PHP
- 518 Python
- 37 Ruby
- 4.3K VB.NET
- 1.6K VBA
- 20.8K Visual Basic
- 2.6K Game programming
- 312 Console programming
- 89 DirectX Game dev
- 1 Minecraft
- 110 Newbie Game Programmers
- 2 Oculus Rift
- 8.9K Applications
- 1.8K Computer Graphics
- 730 Computer Hardware
- 3.4K Database & SQL
- 522 Electronics development
- 1.6K Matlab
- 628 Sound & Music
- 257 XML Development
- 3.3K Classifieds
- 196 Co-operative Projects
- 185 For sale
- 189 FreeLance Software City
- 1.9K Jobs Available
- 600 Jobs Wanted
- 201 Wanted
- 2.9K Microsoft .NET
- 1.7K ASP.NET
- 1.1K .NET General
- 3.3K Miscellaneous
- 4 Join the Team
- 0 User Profiles
- 353 Comments on this site
- 60 Computer Emulators
- 2.1K General programming
- 183 New programming languages
- 604 Off topic board
- 170 Mobile & Wireless
- 44 Android
- 124 Palm Pilot
- 335 Multimedia
- 151 Demo programming
- 184 MP3 programming
- 0 Bash scripts
- 19 Cloud Computing
- 53 FreeBSD
- 1.7K LINUX programming
- 367 MS-DOS
- 0 Shell scripting
- 320 Windows CE & Pocket PC
- 4.1K Windows programming
- 895 Software Development
- 408 Algorithms
- 68 Object Orientation
- 89 Project Management
- 90 Quality & Testing
- 239 Security
- 7.6K WEB-Development
- 1.8K Active Server Pages
- 61 AJAX
- 2 Bootstrap Themes
- 55 CGI Development
- 19 ColdFusion
- 222 Flash development
- 1.4K HTML & WEB-Design
- 1.4K Internet Development
- 2.2K JavaScript
- 34 JQuery
- 286 WEB Servers
- 151 WEB-Services / SOAP

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

Terms of use / Privacy statement / Publisher: Lars Hagelin

Programmers Heaven articles / Programmers Heaven files / Programmers Heaven uploaded content / Programmers Heaven C Sharp ebook / Operated by CommunityHeaven LLC

© 1997-2015 Programmersheaven.com - All rights reserved.

## Comments

1,784Member: 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]

209Member:

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

1,784Member: :

:

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

607Member ✭: : :

: :

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

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.

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!

607Member ✭:

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

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