Running time of a flow-sensitive vs. flow-insensitive analysis

Number of transfer/meet invocations is O(n*h) for a flow-sensitive analysis:

For a flow-sensitive analysis, we know that the maximum number of updates that can happen are O(n*h) where n is the program size, and h is the height of the semi-lattice.
For a flow-insensitive + SSA analysis, it is likely that the size of a value increases by a factor of s, where s is the average number of assignments per variable. This in turn may increase the height h of the semi-lattice (depending on the DFA). Moreover, the size of the program n may increase due to the introduction of phi nodes (say p phi nodes are added). Consequently, if we implement a flow-sensitive analysis on the SSA program, the resulting running time is expected to be worse than executing it on the original program. For the purposes of the rest of the discussion, we will assume that s and p are relatively small compared to |V| and n respectively.
In Kildall's algorithm, every time we pick a worklist item, we either update the DFA value (which gets counted in O(n*h)) or we discard the item (because no updation was performed). The maximum number of such discard events is at most d times the number of updates (where d is the out/in-degree of a node in the CFG). For this analysis we will assume that the average degree d is relatively small compared to n. Thus, the overall number of calls to a transfer-function or the meet-function in a flow-sensitive analysis is O(n*h) under these assumptions.

Number of transfer/meet invocations is again O(n*h) for a flow-insensitive analysis on the SSA program (under the assumptions stated above):

There is only one global value which can have at most h updates.
For each update, we may have to transfer and meet over each instruction in the program, which means that we still have O(n*h) calls to the transfer and meet functions. This is identical to the asymptotic number for a flow-sensitive analysis.

Let's now look at the time taken by a single call to the transfer or meet function or a meet function:

In the flow-sensitive analysis, this involves looking at all the values that may have changed (irrespective of the values referenced in the current statement) and transferring (or meeting them). For a constant-propagation DFA for example, this may be O(n) for a single call.
In the flow-insensitive analysis, this involves looking at only those values that are referenced in the current statement --- for both the transfer and meet functions. For a constant propagation analysis, this is O(1) for a single call.

In general, the complexity of a single transfer or meet function call is expected to be asymptotically smaller (by up to a factor of the size of the values being tracked). For some DFAs, this may not be true, e.g., if the size of a value is always constant-sized; but for many DFAs (e.g., constant propagation, common-subexpression elimination, range analysis, pointer analysis, etc), this yields asympotic improvements by a factor of up to O(n).