Cost analyses of logic programs have been developed which make it possible to obtain automatically lower and upper bounds of runtime cost of computations. This information is very useful for a variety of purposes, including granularity control, query optimization in databases, and program transformation and synthesis. However, current techniques suffer a loss accuracy in some cases which are quite representative (i.e., some divide-and-conquer programs à la QuickSort). This paper describes an alternative probabilistic approach which makes it possible to figure out an estimate of the execution cost. One of its advantages is that it needs only a few changes over previously proposed schemes.