473,327 Members | 1,952 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,327 software developers and data experts.

Big oh Notation

Does anyone know of a good site where I can learn of this?
Jul 17 '05 #1
6 10773
Big O is pretty simple. The O stands for "the Order of" and it shows the
general number of comparisons needed in a sort algorithm. For example, the
average number of comparisons for a selection sort is =N^2/2-N/2. In this
case the N^2 dominates and so the big O notation is O(N^2). For a quicksort
I believe it is =N(log2N) which defined as O(log2 N) because the log2N,
against a large number of items, will dictate the amount of time taken.

Hope this helps a bit.
"jova" <Em***@nospam.net> wrote in message
news:fL*****************@nwrdny02.gnilink.net...
Does anyone know of a good site where I can learn of this?

Jul 17 '05 #2

"Moth" <no*@this.address> wrote in message
news:hS******************@news-server.bigpond.net.au...
Big O is pretty simple. The O stands for "the Order of" and it shows the
general number of comparisons needed in a sort algorithm. For example, the average number of comparisons for a selection sort is =N^2/2-N/2. In this
case the N^2 dominates and so the big O notation is O(N^2). For a quicksort I believe it is =N(log2N) which defined as O(log2 N) because the log2N,
against a large number of items, will dictate the amount of time taken.

Hope this helps a bit.
"jova" <Em***@nospam.net> wrote in message
news:fL*****************@nwrdny02.gnilink.net...
Does anyone know of a good site where I can learn of this?



If only we had a sorting algorithm of O(log2N) :-) Unfortunately both N and
log2N are significant here (N is more then log2N anyway) so you get O(N
log2N).

And for QS that is average behaviour, worst case is O(N^2) also. For a
sorting algorithm with worst-case O(N log2N) you would need something like
HeapSort.

BTW: Big O notation is used for any algorithm category, not only for sorting
algorithms.

Silvio Bierman
Jul 17 '05 #3
Moth wrote:
Big O is pretty simple. The O stands for "the Order of" and it shows the
general number of comparisons needed in a sort algorithm. For example, the
average number of comparisons for a selection sort is =N^2/2-N/2. In this
case the N^2 dominates and so the big O notation is O(N^2). For a quicksort
I believe it is =N(log2N) which defined as O(log2 N) because the log2N,
against a large number of items, will dictate the amount of time taken.
Oh just a little thing you missed i think. Big O notation is the "Worst
Case" notation. Meaning that the worst case is what is going to happen
after the O. For example, the worst case in picking a number of an
array with a simple for loop is O(n). Because n (the number of
elements) is the worst-case scenario (that the number you want is at the
end).

There are two other notations. Big-Omega (I don't have the omega
symbol, but its like the Ohms symbol if you remember that from
electronics) means the best case scenario. For example, if your
element is at the begining of the array.

Now there is another one that talks is 'tight-bound'. This is your
"average" case and is the best to compare two algorithms. Since an algo
could be excellent, but have one very bad case, O notation only shows
the worst case. But the Big-Theta notation shows the average case.

If you are a beginner you can compare with O notation to algorithms, but
if you have done this before or have some math background, i would
suggest comparing with Big-Theta.

For a good site, its usually mathematics sites that have it. Here our
class book. This is probably what you might be you are looking for.

Cormen, Leiserson, Rivest, and Stein: "Introduction to Algorithms",
McGraw Hill, MIT Press.

Or any good Discreet Math book will have it.

Hope this helps a bit.
"jova" <Em***@nospam.net> wrote in message
news:fL*****************@nwrdny02.gnilink.net...
Does anyone know of a good site where I can learn of this?


Jul 17 '05 #4
While it was 2/23/04 9:01 PM throughout the UK, Moth sprinkled little
black dots on a white screen, and they fell thus:
Big O is pretty simple. The O stands for "the Order of" and it shows the
general number of comparisons needed in a sort algorithm. For example, the
average number of comparisons for a selection sort is =N^2/2-N/2. In this
case the N^2 dominates and so the big O notation is O(N^2). For a quicksort
I believe it is =N(log2N)
That looks like it means either:

- the logarithm to some unspecified base of 2N
- the function of logarithm to base 2N

I think you mean N log2 N

or if you want to be a little clearer, N * log_2 N
which defined as O(log2 N) because the log2N,
against a large number of items, will dictate the amount of time taken.


Actually, O(N*log N) is an order in its own right. N*log_2 N is far
from asymptotic to log_2 N - try plotting it and you'll see.

The base can be omitted in that particular O expression, as all logs are
the same order. (That doesn't apply to exponentials, nor I think to log
log N.)

There is actually a strict mathematical definition.

f(n) ~ O(g(n)) means that there exists values N and U such that, for all
n > N, f(n) < U*g(n). So in fact, the O notation denotes an upper bound
- any measure that is O(n) is also O(n^2), etc.

f(n) ~ Omega(g(n)) means that there exists values N and L such that, for
all n > N, f(n) > L*g(n).

f(n) ~ Theta(g(n)) means f(n) ~ O(g(n)) && f(n) ~ Omega(g(n)).

Stewart.

--
My e-mail is valid but not my primary mailbox, aside from its being the
unfortunate victim of intensive mail-bombing at the moment. Please keep
replies on the 'group where everyone may benefit.
Jul 17 '05 #5
I learned about Big-Oh from Concrete Mathematics by Graham, Knuth,
Patashnik, excellent book. And also Donald Knuths monumental (well,
three volumes so far) The Art Of Computer Programming.

And by the way, I'm almost positve that QS is of order O(n log n).
(And even if it isn't most people would write it O(n log n) anyway
because

O(n log 2n) = O(n(log 2 + log n)) = O(n log n + n log 2) = O(n log n)

right?)
Jul 17 '05 #6
Oskar Sigvardsson wrote:
I learned about Big-Oh from Concrete Mathematics by Graham, Knuth,
Patashnik, excellent book. And also Donald Knuths monumental (well,
three volumes so far) The Art Of Computer Programming.

And by the way, I'm almost positve that QS is of order O(n log n).
In the average case, yes. It's O(n^2) worst case, O(n) best case.
(And even if it isn't most people would write it O(n log n) anyway
because

O(n log 2n) = O(n(log 2 + log n)) = O(n log n + n log 2) = O(n log n)


Either something is O(n log n) or it isn't. O(n log 2n) is indeed
identical to O(n log n). An order is an order, not the way some
convention chooses to write it down.

Stewart.

--
My e-mail is valid but not my primary mailbox, aside from its being the
unfortunate victim of intensive mail-bombing at the moment. Please keep
replies on the 'group where everyone may benefit.
Jul 17 '05 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
by: Robert Mark Bram | last post by:
Howdy All! Is there any difference between referencing objects and attributes with dot notation or bracket notation? Example, document.formname.controlname document Can I access...
6
by: S. | last post by:
if in my website i am using the sgml { notation, is it accurate to say to my users that the site uses unicode or that it requires unicode? is there a mathematical formula to calculate a unicode...
17
by: Thomas Lorenz | last post by:
Hello, I'm a little confused about object initialization. According to Stroustrup (The C++ Programming Language, Special Edition, Section 10.2.3) constructor arguments should be supplied in one...
4
by: Matthias | last post by:
I have been told not to use preceding underscores when notating data members for example. What kind of notation do you use in general? I have seen Microsoft uses hungarian notation a lot. Is that...
14
by: John T. | last post by:
I have a number in 8.8 notation that I wish to convert to a float....... 8.8 notation is a 16 bit fixed notation, so: 0xFF11 is the number 255.17 0x0104 is the number 1.4 0x2356 is the number...
2
by: funcSter | last post by:
I was asked to program using the Dutch Notation with C#. I am not familiar with the Dutch notation at all. I use the Hungarian. I asked a programmer friend "What is the Dutch Notation?" He...
19
by: | last post by:
Just seeking some advice (or solace)... Am I the only who's having trouble letting go of notation? Having extensive experience in C++ years ago (both before I jumped into VB3 in college and at...
66
by: CMM | last post by:
So after three years of working in .NET and stubbornly holding on to my old hungarian notation practices--- I resolved to try to rid myself of the habit. Man, I gotta say that it is liberating!!! I...
22
by: bearophileHUGS | last post by:
>From this interesting blog entry by Lawrence Oluyede: http://www.oluyede.org/blog/2006/07/05/europython-day-2/ and the Py3.0 PEPs, I think the people working on Py3.0 are doing a good job, I am...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.