didactics (12)

From the Specification : Big-O Notation

·         Linear time, polynomial time, exponential time.

·         Order of complexity.

Notation

Name

Example

{\displaystyle O(1)\,}

constant

Determining if a number is even or odd; using a constant-size lookup table

{\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)\,}

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!)\,}

linearithmic, loglinear, or quasilinear

Performing a Fast Fourier transform; heapsort, quicksort(best and average case), or merge sort

{\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}

polynomialor algebraic

Tree-adjoining grammar parsing; maximum matching for bipartite graphs

{\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!)\,}

factorial

Solving the travelling salesman problem via brute-force search; generating all unrestricted permutations of a poset; finding the determinant with expansion by minors.