The large-scale process and environmental variations for today's nano-scale ICs are requiring statistical approaches for timing analysis and optimization (1). Significant research has been recently focused on developing new statistical timing analysis algorithms (2), but often without consideration for how one should interpret the statistical timing results for optimization. The invention provides a sensitivity-based metric (2) to assess the criticality of each path and/or arc in the statistical timing graph (4). The statistical sensitivities for both paths and arcs are defined. It is shown that path sensitivity is equivalent to the probability that a path is critical, and arc sensitivity is equivalent to the probability that an arc sits on the critical path. An efficient algorithm with incremental analysis capability (2) is described for fast sensitivity computation that has a linear runtime complexity in circuit size. The efficacy of the proposed sensitivity analysis is demonstrated on both standard benchmark circuits and large industry examples.