1.4 Frequency Count Method

Frequency Count Method

The video explains how to estimate an algorithm’s time and space complexity by counting how often its statements execute.

Methodology

• Assign one unit of time to each statement.
• For statements inside loops, count how many times they run:
  • A loop body that processes n items generally runs n times.
  • A loop condition is checked n + 1 times: once for each successful iteration and once more when it fails.
  • With nested loops, multiply the iteration counts. For example, two loops of size n produce about n² executions of an innermost statement.
• Add the statement counts to form a time function, such as a polynomial in n.
• Identify the polynomial’s highest-degree term to describe its growth rate. The video calls this the algorithm’s “order.”
• To estimate space complexity, count the storage used by arrays and variables, then consider how that amount grows with n.

Examples

• Sum the elements of an array: A loop processes each of the n elements, so the time grows linearly: O(n). The video also describes the space as growing linearly with the array size: O(n).
• Add two n × n matrices: Two nested loops visit each matrix position, giving O(n²) time. The matrices require space proportional to n², so the described space complexity is O(n²).
• Multiply two n × n matrices: Three nested loops make the innermost work occur roughly n³ times, giving O(n³) time. The input and result matrices use space proportional to n², so the described space complexity is O(n²).

The examples illustrate how loop nesting affects time complexity: one loop gives linear growth, two give quadratic growth, and three give cubic growth. The speaker focuses on the highest-degree term rather than preserving constant and lower-order terms.

Speakers or Sources

• Abdul Bari — instructor and sole speaker in the video.