จากรหัสเทียมข้างต้นจะพบว่าการดำเนินการของขั้นตอนวิธีของเบลแมน-ฟอร์ดนั้นจะมีการทำงานอยู่ 2 ส่วนหลัก คือ

1. วงวนที่มีการวนเพื่อตรวจสอบความตึงของน้ำหนักเส้นเชื่อมในกราฟ ซึ่งจะทำงานเป็นเวลานานเท่าจำนวนเส้นเชื่อมที่มี ดังนั้น จะใช้เวลาในการทำงานส่วนนี้เป็น O(|E|) เมื่อ E คือจำนวนเส้นเชื่อมของกราฟหนึ่งๆ
2. ส่วนการทำงานที่ต้องผ่านปมทุกปมในกราฟจะใช้เวลาทั้งหมดเป็น O(|V|) เมื่อ V คือจำนวนปมของกราฟหนึ่งๆ

เพราะฉะนั้นจึงสรุปได้ว่าชั้นตอนวิธีของเบลแมน-ฟอร์ดมีอัตราการเติบโตเท่ากับ O(|V||E|)