A Comparison of the Worst-Case Complexities of Two Algorithms for the Reaching Definitions Problem

Abstract

An algorithm to solve the “reaching definitions” problem on reducible flow graphs is presented. It is based on the concept of a region of a flow graph, and has the worst-case time bound of O(n²) bit-vector operations. The algorithm is compared for time complexity with the well-known round-robin version of the iterative algorithm. The comparison shows that for every flow graph of n>2 nodes the region analysis algorithm for the “reaching definitions” problem requires in the worst case fewer bit-vector operations than the round-robin version of the iterative algorithm for the same problem.