This paper addresses the problem of high computational requirements in the implementation of Set-Valued Observers (SVOs), which places stringent constraints in terms of their use in applications where low computational power is available or the plant is sensitive to delay. It is firstly shown how to determine an overbound for the set-valued estimates, which reduces the overhead by limiting the number of inequalities defining those set-valued state estimates. In the particular setting of distributed gossip problems, the proposed algorithm is shown to have constant complexity. This algorithm is of prime importance to reduce the computational load and enable the use of such estimates for real-time applications. Results are also provided regarding the frequency of the triggers in the worst-case scenario. The performance of the proposed method is evaluated through simulation.