Model predictive control (MPC) with linear cost function for hybrid systems requires the solution of a mixed-integer linear program (MILP) at each sampling time. The branch and bound (B&B) method is a commonly used tool for solving mixed-integer problems. In this work, we present an algorithm to exactly certify the computational complexity of a standard B&B-based MILP solver. By the proposed method, guarantees on worst-case complexity bounds, e.g., the worst-case iterations or size of the B&B tree, are provided. This knowledge is a fundamental requirement for the implementation of MPC in a real-time system. Different node selection strategies, including best-first, are considered when certifying the complexity of the B&B method. Furthermore, the proposed certification algorithm is extended to consider warm-starting of the inner solver in the B&B. We illustrate the usefulness of the proposed algorithm by comparing against the corresponding online MILP solver in numerical experiments using both cold-started and warm-started LP solvers.