Finding the sparse representation of a signal in an overcomplete dictionary has attracted a lot of attention over the past years. In our paper, we analyze the probabilistic average-case performance of ProSparse, a new polynomial complexity algorithm that solves the sparse representation problem when the underlying dictionary is the union of a Vandermonde matrix and a banded matrix. Closed-form expressions for the exact success probabilities of ProSparse are given. We also analyze the success probabilities in the high-dimensional regime, revealing a sharp phase transition phenomenon regarding the performance of the algorithm.