Các công thức cần thiết

Quy tắc tổng quát để phân tích 1 chương trình

• Thời gian của lệnh gán, read, write là O(1)
• Thời gian thi hành của một chuỗi lệnh được xác định bằng qui tắc cộng. Như vậy thời gian thi hành này bằng với thời gian thi hành một lệnh lâu nhất trong chuỗi lệnh
• Thời gian thi hành của lệnh IF là thời gian thi hành lớn nhất trong điều kiện IF hoặc sau ELSE
• Thời gian thực hiện vòng lập là tổng thời gian thực hiện thân vòng lập. Nếu thời gian thực hiện thân vòng lập không đổi thì thời gian thực hiện vòng lập bằng tích thời gian thân vòng lập với số lần lập.

Công thức tính tổng tổng quát