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