idrisr/gist:0f7cd0a1c671ce9e580f5ceb194986e0

## gistfile1.txt
The key thing to understand about big-O notations is that the discussion centers around functions. The input to a Big-O calculation is a function, and the output is another function. The 'O' function is a higher-order function, in that it operates on functions, and returns a function as well.

This is a notion well understood by haskell programmers, and anyone accustomed to using lambda abstractions, which I believe includes nearly all functional programmers. Python programmers are familiar with these ideas from decorators. When I programmed with python, decorators were a head-scratcher, in that once decorators were stacked upon other decorators, I'd be on shaky ground. The use of types greatly illuminates the concepts, so I'll switch to them here.

We can consider the function BigO :: (a -> N) -> (N -> N), where N is the natural numbers and a is a generic. That a in any problem where complexity analysis being applied will typically stand for some data structure like a binary tree or a linked list. It's whatever structure relevant to your computation.

Let's call that first function f :: a -> N. This is what you need to come up with. Say for your algorithm it's a^2 + 10n. Now we feed this to O, and O returns a^2.  Notice that a^2 is a function, as if f(a) = a^2.  It's waiting for any value to be applied to, but in big O we deal with functions, so we just leave it unevaluated.

The final step is to characterize the function returned from O.  The choices are usually are constant, logarithmic, sublinear, linear, n log(n), quadratic, and exponential.

We can think of this as another g :: (N -> N) -> S. Here g takes the output from BigO and characterizes the upper bound function as some element of S. S is a toset, or a totally-ordered-set. That means that we can compare the elements of S against any other element. This is done to simplify everything from functions to single description of the function. This is what is meant when someone says an algorithm is quadratic. They've done is first calculate the number of computations, put that into some function like x^7 + 8x + 123.  We put that through BigO, and BigO will return x^7, because it's ignoring everything except the x^7. Lastly that function gets passed to g, and returns polynomial.

In sum, the calculuation can be composed to g . BigO, which is a function (a -> N) -> S.
	The key thing to understand about big-O notations is that the discussion centers around functions. The input to a Big-O calculation is a function, and the output is another function. The 'O' function is a higher-order function, in that it operates on functions, and returns a function as well.

	This is a notion well understood by haskell programmers, and anyone accustomed to using lambda abstractions, which I believe includes nearly all functional programmers. Python programmers are familiar with these ideas from decorators. When I programmed with python, decorators were a head-scratcher, in that once decorators were stacked upon other decorators, I'd be on shaky ground. The use of types greatly illuminates the concepts, so I'll switch to them here.

	We can consider the function BigO :: (a -> N) -> (N -> N), where N is the natural numbers and a is a generic. That a in any problem where complexity analysis being applied will typically stand for some data structure like a binary tree or a linked list. It's whatever structure relevant to your computation.

	Let's call that first function f :: a -> N. This is what you need to come up with. Say for your algorithm it's a^2 + 10n. Now we feed this to O, and O returns a^2. Notice that a^2 is a function, as if f(a) = a^2. It's waiting for any value to be applied to, but in big O we deal with functions, so we just leave it unevaluated.

	The final step is to characterize the function returned from O. The choices are usually are constant, logarithmic, sublinear, linear, n log(n), quadratic, and exponential.

	We can think of this as another g :: (N -> N) -> S. Here g takes the output from BigO and characterizes the upper bound function as some element of S. S is a toset, or a totally-ordered-set. That means that we can compare the elements of S against any other element. This is done to simplify everything from functions to single description of the function. This is what is meant when someone says an algorithm is quadratic. They've done is first calculate the number of computations, put that into some function like x^7 + 8x + 123. We put that through BigO, and BigO will return x^7, because it's ignoring everything except the x^7. Lastly that function gets passed to g, and returns polynomial.

	In sum, the calculuation can be composed to g . BigO, which is a function (a -> N) -> S.