Problem Solving: Maths for bigO notation
From the Specification : BigO Notation

Big O Notation (also known as BigO Notation) is a mathematical way of describing the limiting behaviours of a function. In other words, it is a way of defining how efficient an algorithm is by how "fast" it will run.
Timing edit
You can work out the time that an algorithm takes to run by timing it:
Dim timer As New Stopwatch()
timer.Start()
For x = 1 to 1000000000
'count to one billion!
Next
timer.Stop()
' Get the elapsed time as a TimeSpan value.
Dim el As TimeSpan = stopWatch.Elapsed
' Format and display the TimeSpan value.
Dim formattedTime As String = String.Format("{0}:{1}:{2}.{3}", el.Hours, el.Minutes, el.Seconds, el.Milliseconds / 10)
Console.WriteLine( "Time Elapsed: " + formattedTime)
However, this isn't always suitable. What happens if you run some code on a 33 MHz processor, and the same code on a 3.4 GHz processor? Timing a function tells you a lot about the speed of a computer, and very little about the speed of an algorithm.
Refining algorithms edit
We might want to write a program to calculate the sum of all the numbers between 0 and a variable N
, where N
in this case == 7483647. To solve this, you might write a solution that has a loop that cycles through each number all the way up to N
, adding it to another variable sum
. The code might look a little like thisː
dim N as integer = 7483647
dim sum as double= 0
for i = 1 to N
sum = sum + i
loop
console.writeline(sum)
It certainly works, but as N
gets larger the program runs more slowly. In fact, there is a relationship between the value of N
and the speed of the algorithm. If you were to double N
, the algorithm would take twice as long and if you were to treble N
, the code would take three times as long. We can describe the speed of this relationship using big O notationː . That is the speed of the algorithm is related to the number of items being processed, in our case N
. This is known as linear time.
We can of course write this is a much faster wayː
dim N as integer = 7483647
dim sum as double = N * (1 + N) / 2
console.writeline(sum)
This version of the algorithm gets the same result, but doesn't use a loop. It completes in the same amount of time whatever value of N
you give it. We can describe this algorithm using big O notation as beingː . That is, it completes in a constant time.
Order of Complexity edit
Notation  Name  Example 

constant  Determining if a number is even or odd; using a constantsize lookup table  
logarithmic  Finding an item in a sorted array with a binary search or a balanced search tree as well as all operations in a Binomial heap.  
linear  Finding an item in an unsorted list or a malformed tree (worst case) or in an unsorted array; Adding two nbit integers by ripple carry.  
linearithmic, loglinear, or quasilinear  Performing a Fast Fourier transform; heapsort, quicksort (best and average case), or merge sort  
quadratic  Multiplying two ndigit numbers by a simple algorithm; bubble sort (worst case or naive implementation), Shell sort, quicksort (worst case), selection sort or insertion sort  
polynomial or algebraic  Treeadjoining grammar parsing; maximum matching for bipartite graphs  
exponential  Finding the (exact) solution to the travelling salesman problem using dynamic programming; determining if two logical statements are equivalent using bruteforce search  
factorial  Solving the travelling salesman problem via bruteforce search; generating all unrestricted permutations of a poset; finding the determinant with expansion by minors. 