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  edit source]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  edit source]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  edit source]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. 