Skip to main content

Big-O

And now for Big-O notation.  It's not about mecha and it involves math... don't worry I'll keep the math light.

Big-O notation is a measure of an algorithms scaling based on input size.  Every operation on a data structure is an algorithm and Big-O lets us know how expensive they are going to be.

As an example lets look at a stack of cards.
Picking the top card off of a stack of cards takes the same amount of time if there are 6 cards in the stack or 600 cards in the stack.  This only every takes 1 operation regardless of the size of the stack so this is O(1).  The operation is constant.  Even if the stack was in a box which needed to be opened first, hence taking 2 operations, this would still be O(1) because it doesn't grow with input size.

Finding a specific card in the stack is more difficult in a stack of 600 than in a stack of 6 however.

On average you have to look at 3 cards on the stack of 6 and 300 cards on the stack of 600.  This means that on average you have to look at the number of cards on the stack N divided by 2.  Big-O notation is only concerned with the order of the growth however so this is written as O(N).  The operation grows linearly with the size of the input.

Common orders you will encounter are,
O(1) - the operation takes constant time
O(log N) - the operation grows at the log of the input
O(N) - the operation grows linearly with the size of the input.
O(N^2) - the operation grows at the square on the input

I give you an idea of the relative scalings lets consider operations on 1,000,000 elements.
At O(1) you will use a constant number of operations.  Meaning, it's the same as it was for only 1 element.
At O(log N) you will use 6 operations.
At O(N) you will use 1,000,000 operations
and at O(N^2) you will use 1,000,000,000,000 operations.

Labels:

Comments

Post a Comment

Popular posts from this blog

Duck typing considered harmful.

I've had a chance to work on a fairly large chunk of Python at this point and have decided that Python (like Perl) is completely untenable at scale.  <rant><rave><drool>  but wait!  I have reasons! Programmers spend most of their time reading code.  We read massive amounts of code.  After we read massive amounts of code we write one... or change one... To make a change to a piece of code you first have to understand what it does and how it interacts with the system around it.  Then we start reading massive amounts of code again.  Anything you can do to minimize the amount of code a programmer has to understand to make a change becomes a huge gain in productivity. Duck typing causes the amount of code you need to read to make a change to grow very large. For example lets look at two functions, one in C++ and one in Python. First in C++ int function(type1 arg1, type2 arg2) {   return arg1->method(arg2); } In this fun...
1 comment
Read more

Types of arrays

Arrays are one of the earliest data structures.  They are essentially just a block of memory which is accessed by offset.  Despite their simplicity there are still several broad categories each with their own sets of algorithms. Is the array a fixed size or can it grow as you add elements to it? A fixed size array is called a static array and one that can grow is called a dynamic array. Are the element all of the same type or can they be different? If they must all be the same type then the array are called homogeneous.  Otherwise it is a heterogeneous array. Finally, how many dimensions (subscripts) does the array have? For example, a 2 dimensioned array is a matrix. The number of dimensions doesn't change the structure of the array but changes the way elements are accessed. 
2 comments
Read more

A Prime Vacation

I like to do small programming exercises to keep my skills sharp.  Unfortunately I sometimes get a little carried away with them. Problem: generate a list of primes numbers. Sounds simple right?  Well lets start to look at this.  First lets define what prime numbers are.  A prime number  is a number which is divisible by only itself and one.  A simple way to test if a number if prime is by  trial division .  To test to see if a number is prime you check whether it is division by any prime less then the square root of that number. The general algorithm for finding the list of primes by trial division is therefore the following. list of primes = {2, 3} for each number begining at 4   check to see if it is divisible by any prime less then the square root of number   if number is prime then append it to list of primes Well go through a sample implementation then see what we can do to improve it.
Post a Comment
Read more