📚 Frequency Count Method of Algorithm Analysis

The frequency count method measures how many times each line (or block) of code is executed, to calculate the running time.

It is one way to analyze the time complexity of an algorithm.

The frequency count method is a simple approach used in algorithm analysis to estimate the time complexity of an algorithm. It involves counting the number of basic operations performed by the algorithm as a function of the input size. The basic operations could be simple arithmetic operations, assignments, comparisons, etc.It involves counting the number of times each basic statement in the algorithm is executed, and then multiplying this count by the time it takes to execute each statement. The total time complexity of the algorithm is then the sum of the time complexities of all of its basic statements.

📚 Example: Linear Search

Problem:Linear search an element x on array arr of size n


int LinearSearch(int arr[], int n,int x)

{
    for( i=0; i<n-1:;i++)
        if (arr[i]==x)
                return i
return -1

}

Assignment Operations:
i = 0 (1 assignment operation)
i++ (n times, where n is the size of the array)

Comparison Operations:
i < n-1 (n times)

Equality Check Operation:

This operation occurs up to n times, depending on the position of x in the array.
arr[i] equals x (up to n times, depending on the position of x in the array)

Return Operation:
return i (1 return operation)

Now, let's express the total frequency as a function of the input size n:

T(n)=1+n+n+n+1=3n+2

In the frequency count method, we again ignore constant factors and lower-order terms. Therefore, the time complexity of this algorithm is O(n).

Summary:
Time Complexity: O(n) - Linear time complexity.

This is a basic illustration of how you can use the frequency count method to analyze the time complexity of an algorithm. Keep in mind that this method provides an estimate and doesn't give an exact measure of time, but it's useful for understanding the general behavior of an algorithm as the input size increases.

🔥 Example : Sum of Elements in an array

int sum(a,n)
{

int sum = 0;
for (int i = 0; i < n; i++) {
    sum = sum + a[i];
}
return sum;
}

Initialization -1 ( sum=0)

Loop control:

• 1 initialization (i=0)
• n+1 comparisons (i<n)
• n increments (i++)

Inside loop = n operations

return -1

So total T(n)= 1 + (1 + n + 1 + n) + n + 1= 3n + 4 steps.

Thus, time complexity = O(n) (linear time).

📚 Example: Bubble Sort

Problem: Sort an array of n elements in ascending order.

---

🔹 Simple C Code for Bubble Sort:

#include <stdio.h>

void bubbleSort(int a[], int n) {
    for (int i = 0; i < n-1; i++) {             // Outer loop
        for (int j = 0; j < n-1-i; j++) {        // Inner loop
            if (a[j] > a[j+1]) {                 // Comparison
                int temp = a[j];                 // Swapping
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
}

int main() {
    int a[] = {5, 1, 4, 2, 8};
    int n = sizeof(a)/sizeof(a[0]);
    bubbleSort(a, n);
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
    return 0;
}

---

📊 Frequency Count Analysis:

Statement	Number of Executions
for (i = 0; i < n-1; i++)	(n-1)+1 = n times (last check fails)
for (j = 0; j < n-1-i; j++)	Varies for each i: sum(n-1, n-2, ..., 1)
if (a[j] > a[j+1])	Each time inner loop runs
Swapping operations	Depends if condition is true (worst case: every time)

🔥 Detailed Calculation:

• Outer loop: runs n-1 times.

• Inner loop:

  • When i=0 → (n-1) times

  • When i=1 → (n-2) times

  • When i=2 → (n-3) times

  • ...

  • When i=n-2 → 1 time

Thus, Total comparisons =

$$(n-1) + (n-2) + (n-3) + \ldots + 1$$

This is the sum of the first $n-1$ natural numbers:

$$\text{Sum} = \frac{(n-1) \times n}{2}$$

Thus, number of comparisons = O(n²)

• Swapping will also happen in the worst case $O(n^2)$ times.

---

For Example: n = 5

Comparisons:

• i = 0 → 4 comparisons

• i = 1 → 3 comparisons

• i = 2 → 2 comparisons

• i = 3 → 1 comparison

Total = 4 + 3 + 2 + 1 = 10 comparisons

(Which is $\frac{5 \times 4}{2} = 10$)

Thus, for n=5, 10 comparisons.

---

🚀 Summary

Aspect	Worst Case Complexity
Comparisons	O(n²)
Swaps	O(n²)
Best case (already sorted, if optimized bubble sort is used)	O(n)

✨ Key Observations:

• Bubble Sort is simple, but very slow for large n.

• Time grows quadratically with n.

• Only good for small arrays or educational purposes.

Advantages of the frequency count method:

• The frequency count method is simple and easy to understand.
• It is a relatively accurate way to estimate the time complexity of an algorithm.
• Frequency count helps in building the foundation for deriving asymptotic notations like Big O, Θ, and Ω.

Disadvantages of the frequency count method:

• The frequency count method can be inaccurate if the time it takes to execute each basic statement is not constant.
• It can be difficult to count the number of times each basic statement is executed for complex algorithms.
• Tracing recursive calls and their internal operations accurately can be complex using this method.

Overall, the frequency count method is a useful and versatile tool for analyzing the time complexity of algorithm

Example:(university question)

What is frequency count? Calculate the frequency count of the statement
x = x+1; in the following code segment
for (i = 0; i< n; i++)
for (j = 1; j< n; j*=2)
    x = x + 1;

Frequency count refers to the number of times a particular statement or operation is executed in a program

Let's analyze the code and calculate the frequency count for the statement x = x + 1;:
The outer loop (for (i = 0; i < n; i++)) runs n times.
The inner loop (for (j = 1; j < n; j *= 2)) runs until j is greater than or equal to n. It effectively runs log2(n) times (since j doubles in each iteration)

Inside the inner loop, x = x + 1; is executed.

Therefore, the total frequency count for the statement x = x + 1; can be calculated as the product of the number of iterations of the outer and inner loops:

Frequency Count=n×log2​(n)