classic example of space/time tradeoff is the lookup table lookup table pre-stores the value of function that would otherwise be computed each time it is needed for example is the greatest value for the factorial function that can be stored in -bit int variable if you are writing program that often computes factorialsit is likely to be much more time efficient to simply pre-compute the storable values in table whenever the program needs the value of nfor < it can simply check the lookup table (if the value is too large to store as an int variable anyway compared to the time required to compute factorialsit may be well worth the small amount of additional space needed to store the lookup table lookup tables can also store approximations for an expensive function such as sine or cosine if you compute this function only for exact degrees or are willing to approximate the answer with the value for the nearest degreethen lookup table storing the computation for exact degrees can be used instead of repeatedly computing the sine function note that initially building the lookup table requires certain amount of time your application must use the lookup table often enough to make this initialization worthwhile another example of the space/time tradeoff is typical of what programmer might encounter when trying to optimize space here is simple code fragment for sorting an array of integers we assume that this is special case where there are integers whose values are permutation of the integers from to this is an example of binsortwhich is discussed in section binsort assigns each value to an array position corresponding to its value for ( = <ni++ [ [ ] [ ]this is efficient and requires th(ntime howeverit also requires two arrays of size next is code fragment that places the permutation in order but does so within the same array (thus it is an example of an "in placesortfor ( = <ni++while ( [ ! /swap element [iwith [ [ ]dsutil swap(aia[ ])function swap(aijexchanges elements and in array (see the appendixit may not be obvious that the second code fragment actually sorts the array to see that this does worknotice that each pass through the for loop will at least move the integer with value to its correct position in the arrayand that during this iterationthe value of [imust be greater than or equal to total of at most swap operations take placebecause an integer cannot be moved out