Logarithm Examples (PDF)

Review Quiz 1  Logarithm Example: Binary Search Binary search: Given an integer X and integers A0,A1,…, AN-1, which are presorted and already in memory, find i such that Ai = X or return i = -1 if X is not in the input. Obvious solution: scan through...

Review Quiz 1  Logarithm Example: Binary Search Binary search: Given an integer X and integers A0,A1,…, AN-1, which are presorted and already in memory, find i such that Ai = X or return i = -1 if X is not in the input. Obvious solution: scan through the list from left to right => T(N) = O(N) Better strategy: If x < middle element => search left side If x > middle element => search right side Logarithm Example: Binary Search (Con’t) template int binarySearch( const vector & a, const Comparable &x) { int low = 0, high = a.size( ) - 1; while( low x ) high = mid - 1; else return mid; // Found } return NOT_FOUND; // NOT_FOUND is defined as -1 } T(N) = T(N/2) + O(1) => T(N) = O( log N ) A good example to keep static records in a sort order is to maintain information about the periodic table of elements. Logarithm Example: Euclid’s Algorithm Computes the greatest common divisor (gcd) of two integers. gcd = largest integer that divides both. Example: gcd(50,15) = 5 The algorithm computes gcd(M,N) assuming M >= N. If N > M swaps them in the first iteration. It computes the remainders until 0 is reached. The last nonzero remainder is the answer. Example: M = 1,989, N = 1,590 the sequence of remainders: 399, 393, 6, 3, 0 => gcd(1989, 1590) = 3. Theorem: After two iterations the remainder is at most half of its original value. The number of iterations is at most 2 log N = O(log N) Logarithm Example: Euclid’s Algorithm long gcd( long m, long n ) { while( n != 0 ) { long rem = m % n; m = n; n = rem; } return m; } Logarithm Example: Euclid’s Algorithm Tracing out the iterations as below: M=1,989, N=1,590 => M%N = 399 M=1,590, N=399 => M%N = 393 M=399, N=393 => M%N = 6 M=393, N= 6 => M%N = 3 M=6, N= 3 => M%N = 0 The remainder doesn’t decrease by a constant factor. Logarithm Example: Exponentiation Compute XN where X, N are integers Obvious algorithm: use N-1 multiplications => O(N) Better algorithm: – If N is even => XN = XN/2 XN/2 – If N is odd => XN = X(N-1)/2 X(N-1)/2 X At most two multiplications are required to halve the problem (N odd). The number of multiplications is 2 log N => T(N) = O(log N)  Example: Exponentiation long pow( long x, int n ) { if( n == 0 ) return 1; if( n == 1 ) return x; if( isEven( n ) ) return pow( x * x, n / 2 ); else return pow( x * x, n / 2 ) * x; } Example: Limitations of Worst-Case Analysis Analysis is empirically to be an overestimate Either the analysis needs to be tightened (clever observation) or average running time is a better choice For many complicated algorithms the worst- case bound is achievable by some bad input so it is an overestimate in practice Average-case analysis is normally extremely complex  Quick Review Mathematical Background – 4 formal definitions Model of Computation – standard repertoire of simple instructions, such as addition, multiplication, comparison and assignment What to Analyze – running time and space Running-Time Calculations This chapter provides some methods on how to analyze the complexity of programs. Unfortunately, it is not a complete guide