A method, apparatus and computer program product predict run-time to completion of workflows executing in a shared multi-tenant distributed compute clusters. The method, apparatus and computer program product receive a MapReduce workflow. The MapReduce workflow includes one or more MapReduce jobs for execution. The method, apparatus and computer program product generates one or more workflow profile summary reports for one or more currently executing workflows on the multi-tenant distributed computing system; generates one or more compact historical workflow profile summary reports of the received MapReduce workflow and the one or more currently executing workflows using the historical reports; generates one or more compact historical cluster contention summary reports of all workflow executing compute clusters in the multi-tenant distributed computing system; and generates a run-time prediction for the MapReduce workflow based at least in part on the one or more currently executing workflow profile summary reports, one or more compact historical workflow profile summary reports, and the one or more compact historical cluster contention summary reports.