ON THE EXPECTED EXECUTION TIME FOR A CLASS OF NON UNIFORM RECURRENCE EQUATIONS MAPPED ONTO 1D REGULAR ARRAYS
В. Н. Александров, Stefka Stoyanova Fidanova · International Journal of Parallel Emergent and Distributed Systems · 1993
A special class non uniform recurrent equations produced data dependency graphs which involve non-constant data dependencies on the input data f(i) is considered. The mathematical expectation of the execution time for the problems described by such recurrences under the assumption that f(i) are uniformly distributed is found. In case when f(i) are exponentially distributed it is proved that the mathematical expectation of time tends to the optimal one.