# Prove the Correctness of Greedy Algorithms

Learn how to prove the correctness of greedy algorithms.

## We'll cover the following

## Restricted search space

A greedy algorithm restricts the search space by selecting the most profitable piece of a solution at each step. For example, the $LargestConcatenate$ algorithm only considers concatenations starting from the largest digit instead of considering all possible concatenations. Instead of all possible ways of changing money, the $Change$ algorithm considers only the ones that include a coin with the largest denomination (that does not exceed $money$).

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.