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

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

- 140.8K All Categories
- 103.6K Programming Languages
- 6.4K Assembler Developer
- 401 Assembly Code Share
- 239 Getting started in assembly
- 4.6K x86 Assembly
- 1.9K Basic
- 97 Qbasic
- 39.9K C and C++
- 5.6K Beginner C/C++
- 330 C/C++ on Linux/Unix
- 450 C/C++ Windows API
- 522 C++ Builder
- 253 C++ Game Development
- 3.3K C++ MFC
- 103 C++.NET
- 404 Visual C++
- 2.9K C#
- 7.9K Delphi and Kylix
- 334 Advanced Delphi
- 360 Delphi beginners
- 4 Haskell
- 9.7K Java
- 56 Enterprise JavaBeans
- 1.3K Java Beginners
- 304 Java Server Pages
- 4.1K Pascal
- 1.3K Perl
- 11 Perl 6
- 2K PHP
- 546 Python
- 37 Ruby
- 4.4K VB.NET
- 258 Advanced VB.Net
- 1.6K VBA
- 20.8K Visual Basic
- 767 Access databases and VB
- 831 Advance Visual Basic
- 1.2K Beginner VB
- 2.6K Game programming
- 315 Console programming
- 90 DirectX Game dev
- 1 Minecraft
- 112 Newbie Game Programmers
- 2 Oculus Rift
- 9K Applications
- 1.8K Computer Graphics
- 279 3D Graphics
- 129 DirectX
- 125 OpenGL
- 740 Computer Hardware
- 9 Cooling & Overclocking
- 3.4K Database & SQL
- 1.1K Access
- 91 ADO Programming
- 288 MySQL
- 358 Oracle
- 440 SQL-Server
- 535 Electronics development
- 1.6K Matlab
- 628 Sound & Music
- 25 DirectSound
- 257 XML Development
- 3.3K Classifieds
- 200 Co-operative Projects
- 198 For sale
- 190 FreeLance Software City
- 1.9K Jobs Available
- 603 Jobs Wanted
- 209 Wanted
- 2.9K Microsoft .NET
- 1.8K ASP.NET
- 1.1K .NET General
- 22 .NET WEB-Services
- 129 .NET WinForms
- 14 .NET XML
- 50 ADO.NET
- 142 C# & VB.NET School Support
- 3.4K Miscellaneous
- 4 Join the Team
- 354 Comments on this site
- 69 Computer Emulators
- 2.1K General programming
- 187 New programming languages
- 621 Off topic board
- 200 Mobile & Wireless
- 72 Android
- 126 Palm Pilot
- 338 Multimedia
- 154 Demo programming
- 184 MP3 programming
- 0 Bash scripts
- 27 Cloud Computing
- 1 Witsbits Go Cloud
- 53 FreeBSD
- 1.7K LINUX programming
- 1 Awk scripting
- 332 Linux Support
- 0 Sed scripting
- 370 MS-DOS
- 0 Shell scripting
- 321 Windows CE & Pocket PC
- 4.1K Windows programming
- 177 COM/DCOM
- 61 Networking And Security
- 17 Windows 2003 Server
- 6 Windows Vista
- 176 Windows XP
- 940 Software Development
- 417 Algorithms
- 68 Object Orientation
- 24 RUP & UML
- 91 Project Management
- 95 Quality & Testing
- 268 Security
- 63 Evil Scripting
- 81 Hacking
- 7.7K WEB-Development
- 1.8K Active Server Pages
- 61 AJAX
- 4 Bootstrap Themes
- 55 CGI Development
- 28 ColdFusion
- 224 Flash development
- 1.4K HTML & WEB-Design
- 1.4K Internet Development
- 131 Mobile Internet & Messaging
- 211 Wireless development
- 2.2K JavaScript
- 37 JQuery
- 304 WEB Servers
- 153 Apache
- 79 IIS
- 150 WEB-Services / SOAP

## Comments

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

:

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

: :

:

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

: : :

: :

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

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

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

:

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

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