472,336 Members | 1,275 Online

# Big oh Notation

Does anyone know of a good site where I can learn of this?
Jul 17 '05 #1
6 10676 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
Does anyone know of a good site where I can learn of this?

Jul 17 '05 #2

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
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
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,... 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... 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)... 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... 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... 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... 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... 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... 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... 0 by: concettolabs | last post by: In today's business world, businesses are increasingly turning to PowerApps to develop custom business applications. PowerApps is a powerful tool... 0 by: better678 | last post by: Question: Discuss your understanding of the Java platform. Is the statement "Java is interpreted" correct? Answer: Java is an object-oriented... 0 by: teenabhardwaj | last post by: How would one discover a valid source for learning news, comfort, and help for engineering designs? Covering through piles of books takes a lot of... 0 by: CD Tom | last post by: This happens in runtime 2013 and 2016. When a report is run and then closed a toolbar shows up and the only way to get it to go away is to right... 0 by: CD Tom | last post by: This only shows up in access runtime. When a user select a report from my report menu when they close the report they get a menu I've called Add-ins... 0 by: Naresh1 | last post by: What is WebLogic Admin Training? WebLogic Admin Training is a specialized program designed to equip individuals with the skills and knowledge... 0 by: jalbright99669 | last post by: Am having a bit of a time with URL Rewrite. I need to incorporate http to https redirect with a reverse proxy. I have the URL Rewrite rules made... 0 by: Matthew3360 | last post by: Hi there. I have been struggling to find out how to use a variable as my location in my header redirect function. Here is my code. ... 0 by: AndyPSV | last post by: HOW CAN I CREATE AN AI with an .executable file that would suck all files in the folder and on my computerHOW CAN I CREATE AN AI with an .executable...