Sign In
Create Account
Follow Us on Twitter
Subscribe on Youtube
2
A few weeks ago my class was being taught about the Big O Notation and I'm doing some revision but it's not really clear to me what it's purpose is... or how it does what it does in simple terms.
Can anyone dumb it down a bit?
Cheers.
5 replies to this topic
Back to top|
|
|
#2
Posted 28 October 2010 - 07:55 PM
Alexander
-
- Moderators
-
- 4,118 posts
It's Science!
- Location:Vancouver, Eh! Cleverness: 200
It is a way to denote algorithmic complexity, or rather time complexity of an algorithm. There are also Big-Omega, Big-Theta, little-O to denote of different bounds and asymptotical growth rates, but those will be getting into subjects that are not completely relevant to your learning programming. In this case big O denotes the limiting behavior of a function when its argument tends towards a particular value or infinity which is useful in computer algorithms, as that is what you will be most likely reaching for with one.
O(1) is another way to denote constant time, where the algorithmic speed is constant no matter what workload, such as adding two numbers or checking if a number is even or odd.
O(n) is linear time, meaning if the workload doubles the algorithmic time will double. An example is finding a key in an unsorted list, or a nested "for" loop to iterate through a list.
O(n log n) or n times the logarithm base 2 of n, is linearithmic and can apply to a sorting algorithm such as quicksort, which is fairly decent in speed. An example of its guts are here: http://www.comp.dit....ing/quickSort.c
O(n^2) is quadratic time, which can apply to bubble sort or insert sort and many others
O(n^3) is cubic time, which is fairly slow and applies to algorithms such as non-smart multiplication of two n*n matrices
O(n!) is factorial time, can apply to larger problems like the traveling salesman problem via brute force.
Without going too much into detail of each time, a nice summary of relevant time complexities can be found here:
Time complexity - Wikipedia, the free encyclopedia
It is always nice to know what your algorithm does, what times it runs in (in best, average and worst case scenarios) and how to improve them.
O(1) is another way to denote constant time, where the algorithmic speed is constant no matter what workload, such as adding two numbers or checking if a number is even or odd.
O(n) is linear time, meaning if the workload doubles the algorithmic time will double. An example is finding a key in an unsorted list, or a nested "for" loop to iterate through a list.
O(n log n) or n times the logarithm base 2 of n, is linearithmic and can apply to a sorting algorithm such as quicksort, which is fairly decent in speed. An example of its guts are here: http://www.comp.dit....ing/quickSort.c
O(n^2) is quadratic time, which can apply to bubble sort or insert sort and many others
O(n^3) is cubic time, which is fairly slow and applies to algorithms such as non-smart multiplication of two n*n matrices
O(n!) is factorial time, can apply to larger problems like the traveling salesman problem via brute force.
Without going too much into detail of each time, a nice summary of relevant time complexities can be found here:
Time complexity - Wikipedia, the free encyclopedia
It is always nice to know what your algorithm does, what times it runs in (in best, average and worst case scenarios) and how to improve them.
Edited by Alexander, 29 October 2010 - 09:44 AM.
Be sure to read the updated FAQ! || Health is achieved through the same 10,000 steps.
If a suggested code/method fails, informing us is less important than telling us why or what errors occurred.
If a suggested code/method fails, informing us is less important than telling us why or what errors occurred.
#3
Posted 28 October 2010 - 08:18 PM
lor
-
- Members
-
- 884 posts
Programming Goddess
So basically the Big O Notation just helps you to figure out how efficient (searching and inserting) your data structure is?...
#4
Posted 28 October 2010 - 08:21 PM
Alexander
-
- Moderators
-
- 4,118 posts
It's Science!
- Location:Vancouver, Eh! Cleverness: 200
The algorithm you use to do so, yes.
Be sure to read the updated FAQ! || Health is achieved through the same 10,000 steps.
If a suggested code/method fails, informing us is less important than telling us why or what errors occurred.
If a suggested code/method fails, informing us is less important than telling us why or what errors occurred.
#5
Posted 28 October 2010 - 08:31 PM
lor
-
- Members
-
- 884 posts
Programming Goddess
#6
Posted 29 October 2010 - 05:26 PM
WingedPanther
-
- Moderators
-
- 16,831 posts
A spammer's worst nightmare
- Location:Upstate, South Carolina
- Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
- Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others
It's also related to the idea of having families of functions in Algebra. For example, there are all the variations on parabolas, which are all variations on y=x^2. y=x^3 is another family of functions. y=e^x is another family. Big-Oh talks about which family it belongs to.
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users
