Approximate computing has emerged as a new design paradigm in wide variety error resilient applications to decrease the hardware cost in an acceptable deviation from the nominal output values. In this paper, a logic approximation technique is proposed which takes advantage of error budget in error tolerant applications to achieve an approximation circuit with smaller area and latency. Moreover, a heuristic is proposed to prune the search space, which increases the scalability of the proposed technique. The results show 38.3% reduction in area and 26.6× speed up compared to the state-of-the-art approximation techniques.