Algorithms – Complexity and the Big-Oh

A friend once told me that you can only truly grasp the idea of complexity if you make friends with the Big-Oh; And that's exactly what i intend to help you all with here today! :)

Complexity

Put quite simply, complexity is the running time of algorithms. We’ve all done it at some point in time or other; gone and wrote a program that we thought would be absolutely amazing – only to find that it takes way too long to run.

Within complexity itself, there are two forms:

1. Time Complexity – which is pretty obvious, its the running time of an algorithm


2. Space Complexity – which is the amount of memory that the algorithm needs

Time and Space Complexity

Sadly I am a little too lazy to type it all out again. Yep, that's right, i have already wrote a post on Time and Space Complexity :D
If your mind it a little rusty, and you need too kick those gears back into motion, then here you go: http://computersciencesource.wordpress.com/2009/09/09/year1-computation-time-space-complexity/

Running Time – On what does it depend?

The running time of an algorithm varies – A LOT!



Lets say you have the source code above – which is a fairly simple version of a Bubble Sort algorithm which will sort numbers into ascending order. But my main question is, can you see why this algorithm will have varying running times?

Yes? No? Well either way i am going to tell you. Look at the third line:

• “array[i] = rand()*10”

No matter what, every time you run that algorithm, the array will have 5 different numbers contained with in it every time. Which means that you could end up with a horrible array that is in descending order (worst case scenario); or you could end up with an array that is already in perfect order (best case scenario).

Note: for this algorithm, the worst case is an approximate of 20 comparisons, where as the best case would only be 4 comparisons.

Functions

For the above algorithm, the simplest way to express the worst case is with a function. Note: This function will only consider the number of comparisons, not the swaps or the initial assignments.


Running times can be expressed as a growing function of the input size n. So for the worst case above it would be:

• f(n) = n(n-1)

Here, the n represents the number of elements contained within the array we need to sort – so the input size.

f(n) represents the number of primitive operations the algorithm performs on an input  of size n.

So with this, we can say that the running time is equal to the growing function:

• t = f(n) = n(n-1)

Comparing Functions

Lets say we have another function, g(n). If we wish to compare these two functions, f(n) and g(n), then we don’t really need to care about how big one function is relative to the other – such as f(n) being 50 times larger than g(n).
The only thing that we really care about is if f(n) is of a different order than g(n).

Put simply, we only really care if the relative size of f(n) to g(n) keeps growing as n does.

2 examples of this are if f(n) = 2n and g(n)=10n.

Here, 2n and 10n are both O(n).

Better Example

Lets say we have the following functions:

• f(n) = (n^2)


• g(n) = n

Here we have two functions. However, the relative size of (n^2) to n grows without bound FOREVER as n grows.

• (n^2)/n  =  n  = not a constant value as n is a variable

Thanks to this, we can say that (n^2) is of a larger order than n.

Another way to write this would be to say that (n^2) is not O(n).

Another Better Example

Don’t worry, this post will nearly be over :)

However, lets now say that we have the two functions:

• f(n)  =  (n^2)+n


• g(n)  =  (n^2)

Here, as n increases, for larger values of n both of the functions will appear to be of the same order. As the “+n” on f(n) will not longer matter if n=1000. If you dont believe me look at the two functions on a graph for large values of n!!

So here it is safe to say that (n^2)+n and (n^2) are both O(n^2).

Simplifying the Big-Oh!

Sometimes we can have an O(h(n)) where h(n) is a stupidly long function. But thankfully we can simplify it all! To do this just identify the fastest growing term, and then write it in its simpliest form – dropping all other terms.

For example:

• O(5n^3 + logn) becomes    O(n^3) as (n^3) is the fastest growing term.