# The Big O Notation

• 04-23-2012, 08:12 PM
dougie1809
The Big O Notation
Hi,

How do you calculate the Big O worst cast scenario for a merge sorting algorithm?
The formula is O(n log n) and say if you have the value of 'n' to be 14.

I really can't get my head around it?

Thanks
• 04-23-2012, 08:23 PM
KevinWorkman
Re: The Big O Notation
What is your actual question? You have already supplied the Big-O 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?
• 04-23-2012, 08:27 PM
dougie1809
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
• 04-23-2012, 08:27 PM
JosAH
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,

Jos
• 04-23-2012, 08:31 PM
dougie1809
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
• 04-23-2012, 08:34 PM
JosAH
Re: The Big O Notation
Quote:

Originally Posted by dougie1809
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

No and no, you can't just plug in a value and expect something reasonable from the answer.

kind regards,

Jos
• 04-23-2012, 08:39 PM
dougie1809
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
• 04-23-2012, 09:00 PM
dougie1809
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?

Thanks
• 04-23-2012, 09:10 PM
JosAH
Re: The Big O Notation
Quote:

Originally Posted by dougie1809
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?

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,

Jos
• 04-23-2012, 09:14 PM
dougie1809
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
• 04-23-2012, 09:17 PM
JosAH
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,

Jos
• 04-23-2012, 09:21 PM
dougie1809
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
• 04-23-2012, 09:33 PM
JosAH
Re: The Big O Notation
Quote:

Originally Posted by dougie1809
Ah ok, that looks promising. Now how did you calculate 36.9468026146? I mean how is log(14) calculated?

I pressed the 'ln' key on my calculator; if you want the base 2 log, note that a-log(x) == b-log(x)/b-log(a). So 2-log(14) == log(14)/log(2) == 3.8073549221. But again, those numbers don't say much in big-Oh computations (that's why a 'ln' is as good as any base log).

kind regards,

Jos
• 04-23-2012, 09:39 PM
dougie1809
Re: The Big O Notation
Ok, thanks for you help, I understand how this could get complicated when dealing with larger data set. But thanks again.