~ Big O Notation


Big O Notation (also known as Big-O 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

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)
Code Output

Time Elapsed: 0:0:21:3249


However, this isn't always suitable. What happens if you run some code on a 33MHz processor, and some code on a 3.4GHz 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

dim N as integer = 7483647
dim sum as double= 0
for i = 1 to N
   sum = sum + i
loop
console.writeline(sum)

optimised version

dim N as integer = 7483647
dim sum as double =  N * (1 + N) / 2
console.writeline(sum)

Order of Complexity

NotationNameExample
{\displaystyle O(1)\,}{\displaystyle O(1)\,} constant Determining if a number is even or odd; using a constant-size lookup table
{\displaystyle O(\log n)\,}{\displaystyle O(\log n)\,} 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.
{\displaystyle O(n)\,}{\displaystyle O(n)\,} linear Finding an item in an unsorted list or a malformed tree (worst case) or in an unsorted array; Adding two n-bit integers by ripple carry.
{\displaystyle O(n\log n)=O(\log n!)\,}{\displaystyle O(n\log n)=O(\log n!)\,} linearithmic, loglinear, or quasilinear Performing a Fast Fourier transform; heapsort, quicksort (best and average case), or merge sort
{\displaystyle O(n^{2})\,}{\displaystyle O(n^{2})\,} quadratic Multiplying two n-digit numbers by a simple algorithm; bubble sort (worst case or naive implementation), Shell sort, quicksort (worst case), selection sort or insertion sort
{\displaystyle O(n^{c}),\;c>1}{\displaystyle O(n^{c}),\;c>1} polynomial or algebraic Tree-adjoining grammar parsing; maximum matching for bipartite graphs
{\displaystyle O(c^{n}),\;c>1}{\displaystyle O(c^{n}),\;c>1} exponential Finding the (exact) solution to the travelling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute-force search
{\displaystyle O(n!)\,}{\displaystyle O(n!)\,} factorial Solving the travelling salesman problem via brute-force search; generating all unrestricted permutations of a poset; finding the determinant with expansion by minors.
Text is available under the Creative Commons Attribution-ShareAlike License https://en.wikibooks.org/wiki/A-level_Computing