1

Hi...!

In Design of Algorithm.
I think it is used to calculate the time complexity....

What is meant by STEP-COUNT METHOD?
What is the procedure in that to calculate?

I want brief explination. ....

3
Contributors
5
Replies
29
Views
6 Years
Discussion Span
Last Post by arina_1
1

What is meant by STEP-COUNT METHOD?

You define what a "step" means for the algorithm (usually statements), then the total of those steps using variables such as N can be calculated.

What is the procedure in that to calculate?

  • First define steps:
    int mean(int a[], size_t n)
    {
        int sum = 0;                 // 1 step
        for (int i = 0; i < n; i++)  // 1 step
            sum += a[i];             // 1 step
        return sum;                  // 1 step
    }
  • Next determine the frequency of the steps based on N:
    int mean(int a[], size_t n)
    {
        int sum = 0;                 // 1 step * 1
        for (int i = 0; i < n; i++)  // 1 step * (N+1)
            sum += a[i];             // 1 step * N
        return sum;                  // 1 step * 1
    }
  • Add up the steps: 1 + (N+1) + N + 1
  • Reduce: 2N + 3
  • Throw away factors that don't grow with N and you're done: O(N)
0

Thank You......!

How can we say that

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

is "N+1" times. Is it is the case that the loop itarates for "N+1" Number of times?

In the same manner how can we say

sum += a[i];

is it runs for "N" times?

1

Is it is the case that the loop itarates for "N+1" Number of times?

The loop iterates N times, but the statement is executed N+1 times. For example, if N is 0, the loop doesn't iterate but the condition must still be tested. Thus the statement is executed 0+1 times.

In the same manner how can we say

The loop body runs N times. That should be obvious.

0
#include<stdio.h>
int main()
{
    int array[100],maximum,size,c,location=1;
    printf("Enter the number of elemets in array\n");
    scanf("%d",&size);
    printf("Enter %d integers\n",size);
    for(c=0;c<size;c++)
    scanf("%d",&array[c]);
    maximum=array[0];
    for(c=1;c<size;c++)
    {
    if(array[c]>maximum)
    {
    maximum=array[c];
    location=c+1;}
}
printf("maximum element is present at location %d and its value is %d.\n",location,maximum);
return 0;
}

*how to calculatethe number of steps for this algorithm?

Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.