big O notation (so called because it uses the symbol O) describes the limiting behavior of a function for very small or very large arguments, usually in terms of simpler functions. It is also called Big Oh notation, Landau notation, Bachmann-Landau notation, and asymptotic notation. There are also other symbols o, Ω, ω, and Θ for related bounds.
Although developed as a part of pure mathematics, it is now frequently also used in computational complexity theory to describe how the size of the input data affects an algorithm's usage of computational resources (usually running time or memory). It is also used in many other fields to provide similar estimates.
Big-O notation is used to express an ordering property among functions. In the context of our study of algorithms, the functions are the amount of resources consumed by an algorithm when the algorithm is executed. This function is usually denoted T(N). T(N) is the amount of the resource (usually time or the count of some specific operation) consumed when the input to the algorithm is of size N.
Sometimes it is not obvious what the ``size'' of the input is, so here are few examples:
- Multiplication
If we multiply two numbers together using the algorithm we learned in grade school, the number of single-digit multiplications and additions that we do depends on the number of digits in the two numbers being multiplied. (If we multiply two numbers together using a calculator, then the number of keystrokes we need to type also depends on the number of digits in the two numbers.) Therefore, for an algorithm that performs multiplication (or any other arithmetic operation) the ``size'' of the input is usually the number of digits in the input numbers.
(As an aside, remember that most modern computers can perform arithmetic operations on reasonably-sized numbers (i.e. numbers that are 32 or 64 bits in length) in a single instruction, regardless of the number of non-zero digits in the numbers. Therefore, for most purposes, we will assume that arithmetic operations take a constant amount of time. There are many important applications that deal with numbers large enough so that this is not the case, however.)
- Searching
If we have a set of N unknown items, arranged in an unknown order, and we want to do something involving all of them, then the size of the problem is N. For example, if we want to find the smallest element in an array of N numbers, then the size of the problem is N.
The big-O complexity of an algorithm is important, but it does not tell the entire story. Any honest and complete analysis of an algorithm should attempt to address the question of what the real cost of executing the algorithm is for real or typical problems.
For example, imagine that (through some some wonderful twist of fate), you must choose between job offers from two companies. The first company offers a contract that will double your salary every five years. The second company offers you a contract that gives you a raise of $1000 per year. Your salary at the first company increases at 
, while your salary at the second company increases at a rate of O(n). Which position would you choose?
From this information, it is impossible to say. If your starting salaries are the same at the two companies, then what the starting salary is will make all the difference (and if the first company gives you a starting salary of $0, then you are really in trouble!). If the starting salary at the second company is much higher than the first company, then even the wonderful raises the first company offers might not actually make any difference before you retire. In this case, n isn't going to get too large (assuming an ordinary career), so the behavior of your salary as you become infinitely old is not an issue.
E-Store
big O notation (so called because it uses the symbol O) describes the limiting behavior of a function for very small or very large arguments, usually in terms of simpler functions. It is also called Big Oh notation, Landau notation, Bachmann-Landau notation, and asymptotic notation. There are also other symbols o, Ω, ω, and Θ for related bounds.
Although developed as a part of pure mathematics, it is now frequently also used in computational complexity theory to describe how the size of the input data affects an algorithm's usage of computational resources (usually running time or memory). It is also used in many other fields to provide similar estimates.
Big-O notation is used to express an ordering property among functions. In the context of our study of algorithms, the functions are the amount of resources consumed by an algorithm when the algorithm is executed. This function is usually denoted T(N). T(N) is the amount of the resource (usually time or the count of some specific operation) consumed when the input to the algorithm is of size N.
Sometimes it is not obvious what the ``size'' of the input is, so here are few examples:
If we multiply two numbers together using the algorithm we learned in grade school, the number of single-digit multiplications and additions that we do depends on the number of digits in the two numbers being multiplied. (If we multiply two numbers together using a calculator, then the number of keystrokes we need to type also depends on the number of digits in the two numbers.) Therefore, for an algorithm that performs multiplication (or any other arithmetic operation) the ``size'' of the input is usually the number of digits in the input numbers.
(As an aside, remember that most modern computers can perform arithmetic operations on reasonably-sized numbers (i.e. numbers that are 32 or 64 bits in length) in a single instruction, regardless of the number of non-zero digits in the numbers. Therefore, for most purposes, we will assume that arithmetic operations take a constant amount of time. There are many important applications that deal with numbers large enough so that this is not the case, however.)
If we have a set of N unknown items, arranged in an unknown order, and we want to do something involving all of them, then the size of the problem is N. For example, if we want to find the smallest element in an array of N numbers, then the size of the problem is N.
The big-O complexity of an algorithm is important, but it does not tell the entire story. Any honest and complete analysis of an algorithm should attempt to address the question of what the real cost of executing the algorithm is for real or typical problems.
For example, imagine that (through some some wonderful twist of fate), you must choose between job offers from two companies. The first company offers a contract that will double your salary every five years. The second company offers you a contract that gives you a raise of $1000 per year. Your salary at the first company increases at
, while your salary at the second company increases at a rate of O(n). Which position would you choose?
From this information, it is impossible to say. If your starting salaries are the same at the two companies, then what the starting salary is will make all the difference (and if the first company gives you a starting salary of $0, then you are really in trouble!). If the starting salary at the second company is much higher than the first company, then even the wonderful raises the first company offers might not actually make any difference before you retire. In this case, n isn't going to get too large (assuming an ordinary career), so the behavior of your salary as you become infinitely old is not an issue.