summations notation that appears again and again in the analysis of data structures and algorithms is the summationwhich is defined as followsb (if (af ( ( ( ) = where and are integers and < summations arise in data structure and algorithm analysis because the running times of loops naturally give rise to summations using summationwe can rewrite the formula of proposition as ii= ( likewisewe can write polynomial (nof degree with coefficients ad as (nai ni = thusthe summation notation gives us shorthand way of expressing sums of increasing terms that have regular structure the exponential function another function used in the analysis of algorithms is the exponential functionf (nbn where is positive constantcalled the baseand the argument is the exponent that isfunction (nassigns to the input argument the value obtained by multiplying the base by itself times as was the case with the logarithm functionthe most common base for the exponential function in algorithm analysis is for examplean integer word containing bits can represent all the nonnegative integers less than if we have loop that starts by performing one operation and then doubles the number of operations performed with each iterationthen the number of operations performed in the nth iteration is we sometimes have other exponents besides nhoweverhenceit is useful for us to know few handy rules for working with exponents in particularthe following exponent rules are quite helpful