$ and $o(..)$ $)
are notations generally used in asymptotic algorithm analysis for representing the 'cost' of a particular sequence of operations in terms of the amount of time or space they take up. They characterise and group functions based on their growth rates. Formally (I might mess up this definition, it's been a few years since I went through it properly),
) > O(g(x))$ $)
if there exists some
x such that
 > C \cdot g(x)$ $)
for some arbitrarily large
C. I've never required little-O notation, but I believe it applies the above definition but with 'some arbitrarily large' replaced with 'any'.
These definitions receive extensive use in computer science, because they allow one to abstract out the details of algorithms to obtain a general overview of their growth rate.
Example! Consider the following procedure to determine all the prime numbers from 2..n:
Code:
for each potential prime p from 2..n:
could_be_prime = true
for each potential divisor d from 2..p:
if p == 0 (mod d):
// we have found a divisor. this p value can no longer be prime
could_be_prime = false
// we have gone through all potential divisors now.
// if could_be_prime is set, this number has no divisors > 2
if could_be_prime:
this value of p is prime!
For each potential prime (roughly
n) of these), we have to iterate through up to
n numbers. We say this algorithm has time complexity
$ $)
. There are minor speedups that can be made: for example, one can observe that we only need to test values of
d up to half of
n. However, because this doesn't change the
growth rate of the function, we don't care -- it's still
. If we were to observe that we only need to test values of
d up to the square root of
p, this WOULD change the growth rate of the function. It is now
$ $)
.
Theoretical computer science (the area I'm interested in, which is actually a branch of mathematics and not a science at all) is all about discovering, comparing and classifying algorithms like these.
This is actually an area that I know a lot about
unlike most of what's discussed in this thread.
