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

Printable View

- 04-23-2012, 09:12 PMdougie1809The 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, 09:23 PMKevinWorkmanRe: 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, 09:27 PMdougie1809Re: 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, 09:27 PMJosAHRe: 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, 09:31 PMdougie1809Re: 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, 09:34 PMJosAHRe: The Big O Notation
- 04-23-2012, 09:39 PMdougie1809Re: 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, 10:00 PMdougie1809Re: 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, 10:10 PMJosAHRe: 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,

Jos - 04-23-2012, 10:14 PMdougie1809Re: 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, 10:17 PMJosAHRe: 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, 10:21 PMdougie1809Re: 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, 10:33 PMJosAHRe: The Big O Notation
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, 10:39 PMdougie1809Re: 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.