A-level Computing/AQA/Problem Solving, Programming, Operating Systems, Databases and Networking/Problem Solving/BigO notation
From Wikibooks, open books for an open world
< A-level Computing | AQA | Problem Solving, Programming, Operating Systems, Databases and Networking | Problem Solving
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 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[edit]
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)
Notation | Name | Example |
---|---|---|
constant | Determining if a number is even or odd; using a constant-size 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 n-bit 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 n-digit 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 | Tree-adjoining 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 brute-force search | |
factorial | Solving the travelling salesman problem via brute-force search; generating all unrestricted permutations of a poset; finding the determinant with expansion by minors. |