# Thread: The Big O Notation

1. Senior Member
Join Date
Nov 2011
Posts
116
Rep Power
0

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

2. ## 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?

3. Senior 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

4. ## 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

5. Senior 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

6. ## Re: The Big O Notation

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

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

8. Senior 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?

Thanks
Last edited by dougie1809; 04-23-2012 at 09:02 PM.

9. ## Re: The Big O Notation

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

10. Senior 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

11. ## 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

12. Senior 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

13. ## Re: The Big O Notation

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

14. Senior Member
Join Date
Nov 2011
Posts
116
Rep Power
0

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

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•