Results 1 to 14 of 14
Thread: The Big O Notation
 04232012, 08:12 PM #1Senior Member
 Join Date
 Nov 2011
 Posts
 116
 Rep Power
 0
 04232012, 08:23 PM #2
Re: The Big O Notation
What is your actual question? You have already supplied the BigO runtime of mergesort. Are you asking how to get O(n lgn) in the first place, or are you asking how to plug 14 in for n?
How to Ask Questions the Smart Way
Static Void Games  GameDev tutorials, free Java and JavaScript hosting!
Static Void Games forum  Come say hello!
 04232012, 08:27 PM #3Senior Member
 Join Date
 Nov 2011
 Posts
 116
 Rep Power
 0
Re: The Big O Notation
Yes how to plug 14 in for n, and to get a result of the amount of steps it took for that algorithm? (But not in code, Just in theory)
Thanks
 04232012, 08:27 PM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,963
 Blog Entries
 7
 Rep Power
 22
Re: The Big O Notation
Also note that O(f(n)) == O(c*f(n)) where c is any constant, so if you plug in a (small) value for n, the answer by itself doesn't tell you anything.
kind regards,
JosI have the stamina of a seal; I lie on the beach instead of running on it.
 04232012, 08:31 PM #5Senior Member
 Join Date
 Nov 2011
 Posts
 116
 Rep Power
 0
Re: The Big O Notation
Is that another formula for merge or something? I mean can I not just use the basic O(n log n) merge formula to plug in the value?
Thanks
 04232012, 08:34 PM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,963
 Blog Entries
 7
 Rep Power
 22
 04232012, 08:39 PM #7Senior Member
 Join Date
 Nov 2011
 Posts
 116
 Rep Power
 0
Re: The Big O Notation
Ok, what would be the easiest way to calculate the Big O if you have 14 data records that you want to sort in theory? That's really all my problem?
Thanks
 04232012, 09:00 PM #8Senior Member
 Join Date
 Nov 2011
 Posts
 116
 Rep Power
 0
Re: The Big O Notation
The bubble sort is an O(n^2) formula, so if the value of n is 14, then :
O(n^2)
= 14^2
=196
So therefore is took the bubble sort 196 steps to complete the sort.
Now I am sure it would be as simple to do a calculation for the merge O(n log n)?
I just can't plot them in?
Any suggestions?
ThanksLast edited by dougie1809; 04232012 at 09:02 PM.
 04232012, 09:10 PM #9
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,963
 Blog Entries
 7
 Rep Power
 22
Re: The Big O Notation
You seem to want to count the number of elementary operations needed by your sorting algorithm; increment a simple counter each time your algorithm performs one of those elementary operations. A compare or a swap or a single append to a list etc. count as simple operations.
kind regards,
JosI have the stamina of a seal; I lie on the beach instead of running on it.
 04232012, 09:14 PM #10Senior Member
 Join Date
 Nov 2011
 Posts
 116
 Rep Power
 0
Re: The Big O Notation
Oh yes, I do understand how it may be written in code, but I'd like to be able to write it down as an equation i.e.
: O(n log n)
= 14 log(14)
= ??
Id like to calculate in that kind of sense, the same way the bubble sort O(n^2) can be calculated?
Thanks
 04232012, 09:17 PM #11
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,963
 Blog Entries
 7
 Rep Power
 22
Re: The Big O Notation
Well, 14*log(14) == 36.9468026146, but that number doesn't say much (see my first reply in this thread).
kind regards,
JosI have the stamina of a seal; I lie on the beach instead of running on it.
 04232012, 09:21 PM #12Senior Member
 Join Date
 Nov 2011
 Posts
 116
 Rep Power
 0
Re: The Big O Notation
Ah ok, that looks promising. Now how did you calculate 36.9468026146? I mean how is log(14) calculated?
Thanks
 04232012, 09:33 PM #13
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,963
 Blog Entries
 7
 Rep Power
 22
Re: The Big O Notation
I pressed the 'ln' key on my calculator; if you want the base 2 log, note that alog(x) == blog(x)/blog(a). So 2log(14) == log(14)/log(2) == 3.8073549221. But again, those numbers don't say much in bigOh computations (that's why a 'ln' is as good as any base log).
kind regards,
JosI have the stamina of a seal; I lie on the beach instead of running on it.
 04232012, 09:39 PM #14Senior Member
 Join Date
 Nov 2011
 Posts
 116
 Rep Power
 0
Similar Threads

BigO Notation
By kraigballa in forum New To JavaReplies: 9Last Post: 02232012, 03:17 AM 
+= notation
By sehudson in forum New To JavaReplies: 2Last Post: 03112011, 05:51 AM 
Big O notation
By simorgh in forum Advanced JavaReplies: 18Last Post: 07102010, 03:26 PM 
Big O notation
By vendetta in forum New To JavaReplies: 6Last Post: 01082010, 08:47 PM 
Big O Notation
By dsym@comcast.net in forum New To JavaReplies: 1Last Post: 02212009, 07:02 PM
Bookmarks