Did you have this problem before they replaced your master cylinder? If not, then check the vacume line from the break booster to the manifold. It could be missing or broken leading to a major vacume leak.

As a matter of fact, check all your vacume lines.

If you did not have this problem before having you car worked on, then they did something or left something off, or as usual, something broke as a result of fixing something else.

Lawren.