big o notation

This is a discussion on big o notation within the C++ Programming forums, part of the General Programming Boards category; what is big O notation? thanks...

  1. #1
    Registered User heat511's Avatar
    Join Date
    Dec 2001
    Posts
    169

    big o notation

    what is big O notation?

    thanks

  2. #2
    Registered User
    Join Date
    Aug 2001
    Posts
    14
    It's a way to meassure the amount of time a procedure takes from completion to end for a given set of data.

    Let's say you are about to sort an array of lenght n, depending on the sortingalgorithm's design, the time may differ alot.

    For example, I believe bubble-sort sorts the array in O(n^2)
    while for example heapsort sorts the array in O(n log n) time.

    basically this notation is not used for computing exact time, but to compare different algoritms... constant's (x * n^0) are ignored, since the only thing that matters is the power of n.

    This is a quite complicated area and not easy to explain, perhaps this made it somewhat clearar anyway.

    /Laos

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >what is big O notation?
    A theoretical measure of the execution of an algorithm. Since it's an approximation, O-notation tends to be very simple. A long complicated algorithmic equation can be shortened to something like O(n2) in O-notation simply by removing the parts that don't matter, such as constants.

    -Prelude
    My best code is written with the delete key.

  4. #4
    Registered User heat511's Avatar
    Join Date
    Dec 2001
    Posts
    169

    .....errrrrrrr

    that sorta helped

    so basically its a method used to compare how efficient a certain part of code is?

    sorry, I have to write a 2 page paper on big o notation for school and am having trouble finding examples that make sense online

    thanks

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    This may help, but O-notation is a complicated subject which few seem to be able to describe effectively. It's something you can understand but not be able to explain to someone who doesn't understand:
    http://www.cs.wisc.edu/~hasti/cs367-...OMPLEXITY.html

    -Prelude
    My best code is written with the delete key.

  6. #6
    Evil Member
    Join Date
    Jan 2002
    Posts
    638
    Basically, big O notation is used for measuring the speed of an algorithm. Typically it is used for algorithms on containers. N means the number of elements in a container.

    For example, a standard bubble sort is on the order of O(n^2), or quadratic time. This means that the time it takes increases as the square of the number of elements, or doubling the length of the list quadruples the time it takes to bubble sort. This would obviously be very undesirable for a very large container.

    A cheaper algorithm, like a memberwise copy, would be on the order of O(N). This, also known as linear time, means doubling the length of the container doubles the time it takes.

    There is also the O(log(N)). This, known as logarithmic time, means that the speed increases as the log of the number of elements. This is, generally, quicker than constant time.

    The cheapest algorithm, like back insertion to a vector, would be on the order of O(1). This, also known as constant time, means that the number of elements in the container does not affect the time an operation takes. Obviously, this is the most preferable for large containers.

    Some operations can be on combined orders, like O(N*log(N)), and even much worse orders, like O(N^3).

    Also, there is also a + symbol sometimes used. This is known as amortized time. It indicates that the speed may be affected in some situations. For example, insertion into the middle of a vector, with pushing back all the other member, is generally O(N). But, sometimes more space must be allocated for the extra element. This would take substantially longer, but would not happen every time. so it is often written as O(N)+, or amortized linear time.

    The big O notation does not give you a clear measure of the time it take for an operation, it gives a comparison of the speed of an operation based on list size. Sometimes O(N^2) operations are faster than O(N) operations, if the list is very small and the quadratic is substantially more efficient per iteration. But in the large scale, the more efficient the better.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. big O notation question
    By l2u in forum C++ Programming
    Replies: 7
    Last Post: 11-08-2008, 02:53 PM
  2. Big Oh Notation problem
    By vaibhav in forum C++ Programming
    Replies: 4
    Last Post: 04-01-2006, 08:02 AM
  3. about big O notation
    By deepakkrmehta in forum C Programming
    Replies: 3
    Last Post: 08-27-2005, 02:31 PM
  4. Big Oh notation, help me notate this
    By Jeremy G in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 05-12-2005, 03:27 PM
  5. Big O Notation
    By Drew in forum C++ Programming
    Replies: 1
    Last Post: 09-30-2001, 01:22 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21