Polymorphic Time Systems for Estimating Program Complexity

We present a new approach to static program analysis that permits each expression in a program to be assigned an execution time estimate. Our approach uses a time system in conjunction with a conventional type system to compute both the type and the time of an expression. The time of an expression is either an integer upper bound on the number of ticks the expression will execute, or the distinguished element long that indicates that the expression contains a loop and thus may run for an arbitrary length of time. Every fuction typ