algorithm analysis clearlyall the work done inside the loop takes ( per iterationso the analysis requires determining the number of times around the loop the loop starts with high low and finishes with high low >- every time through the loopthe value high low must be at least halved from its previous valuethusthe number of times around the loop is at most log( ) (as an exampleif high low then the maximum values of high low after each iteration are - thusthe running time is (log nequivalentlywe could write recursive formula for the running timebut this kind of brute-force approach is usually unnecessary when you understand what is really going on and why binary search can be viewed as our first data-structure implementation it supports the contains operation in (log ntimebut all other operations (in particularinsertrequire (ntime in applications where the data are static ( insertions and deletions are not allowed)this could be very useful the input would then need to be sorted oncebut afterward accesses would be fast an example is program that needs to maintain information about the periodic table of elements (which arises in chemistry and physicsthis table is relatively stableas new elements are added infrequently the element names could be kept sorted since there are only about elementsat most eight accesses would be required to find an element performing sequential search would require many more accesses euclid' algorithm second example is euclid' algorithm for computing the greatest common divisor the greatest common divisor (gcdof two integers is the largest integer that divides both thusgcd( the algorithm in figure computes gcd(mn)assuming > (if mthe first iteration of the loop swaps them the algorithm works by continually computing remainders until is reached the last nonzero remainder is the answer thusif , and , then the sequence of remainders is thereforegcd( as the example showsthis is fast algorithm as beforeestimating the entire running time of the algorithm depends on determining how long the sequence of remainders is although log seems like good answerit is not at all obvious that the value of the remainder has to decrease by constant factor long long gcdlong long mlong long whilen ! long long rem nm nn remreturn mfigure euclid' algorithm