Complexity Calculation - Frequency Count Method

Frequency Count Method

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.

Let's break down the frequency count method with an example:

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.

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.
• It is can be used to analyze a wide variety of different algorithms.

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.

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

Consider the following scenario

Example 1:

for(i=1;i<=n;i++) // i=1, 2, ..., n Total = n 

  for(j=1;j<=i;j++) 

           expression; 

                    // i=1 -> j=1 Total = 1

                    // i=2 -> j=1, 2 Total = 2 

                    // ... 

                    // i=n -> j=1, 2, ..., n Total = n

So the expression is executed 1+2+...+n times which is (n+1)*n/2

i=1; // 1 

i<=n; // n+1 

i++; // n 

j=1; // n 

j<i; // ((n+2)*(n+1)/2) - 1  =n^2 ; (2+3+...+(n+1)) 

j++; // (n+1)*n/2=n^2

Example-2:

for (i = 0; i< n; i++)

    for (j = 0; j< n; j++)

        x = x + 1;.

here the expression x=x+1 executes n times in the inner loop(j) and the inner loop executes n times for each iteration of outer loop(i). So the expression x=x+1 executes n^2 time.

Analysis of Bubble sort Algorithm

for (int i = 0; i < n-1; i++) { 

    for (int j = 0; j < n-i-1; j++) {

     if (arr[j] > arr[j+1]) 

            { swap(&arr[j], &arr[j+1]);}

Now, let's break down the frequency count analysis:

Outer Loop (i):

Assignment operation: 1 operation (for the entire loop)

Comparison operation: n operations (for each iteration)

Increment operation: n operations (for each iteration)

Inner Loop (j):

Assignment operation: n operations (for each iteration of the outer loop)

Comparison operation: n^22 operations (total for all iterations of the outer loop)

Increment operation: n^2 operations (total for all iterations of the outer loop)

Comparison and Swap Operation:

Inside the inner loop, there is an if statement with a comparison operation (arr[j] > arr[j+1]) and a swap operation if the condition is true. This comparison and swap operation execute n^2 times.

Total Frequency:T(n)=1+n+n+n+n^2+n^2+n^2
Simplifying,:T(n)=3n^2+4n+1

In the frequency count method, we ignore constant factors and lower-order terms. Therefore, the time complexity of Bubble Sort is O(n^2).

Worst-Case Time Complexity

The worst-case time complexity of the bubble sort algorithm occurs when the array is initially sorted in reverse order. In this case, the algorithm will need to perform a quadratic number of comparisons and swaps to sort the array.So the complexity is O(n^2).

Best-Case Time Complexity

The best-case time complexity of the bubble sort algorithm occurs when the array is already sorted. In this case, the algorithm will only need to perform a linear number of comparisons to verify that the array is sorted.So the complexity O(n).

Average-Case Time Complexity

The average-case time complexity of the bubble sort algorithm is also O(n^2). This is because the algorithm is likely to perform a quadratic number of comparisons and swaps for most input arrays.

Conclusion

The bubble sort algorithm is a simple and easy-to-understand sorting algorithm, but it has a relatively high time complexity of O(n^2). This means that the algorithm can become very slow for large input arrays. However, the bubble sort algorithm can be useful for sorting small arrays or for sorting arrays that are already nearly sorted.

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)