Step-Count Method in Algorithm

[Anil2447]

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. ....

[Narue]

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)

[Anil2447]

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?

[Narue]

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.

[Anil2447]

Thank You very Much.....!

[arina_1]

#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?