Copyright © University of Cambridge. All rights reserved.

'How Does Your Function Grow?' printed from https://nrich.maths.org/

Show menu


For many applications mathematicians are not concerned about the exact numerical values of functions but, rather, their behaviour for large values of the variable. Why? One important reason is in the generation of algorithms for implementation on computers: it is often possible to relate the time that the algorithm will take to complete in terms of a simple mathematical function of the number of variables going into the algorithm. Algorithms which take too long to complete will be practically useless, although they may be theoretically beautiful.

An example is the following test, discovered in the 18th century by John Wilson, to see if a number is prime or not:

p is a prime number if and only if (p-2)! = 1mod p

Try using this and you will discover that it is highly inefficient as a way of actually testing for primality, although it is a very beautiful result mathematically.