CODEWITHSUNDEEP
algorithmcomplexity-theory
user2377778
user2377778

Reputation: 73

Step Count in Algorithm

What is the step count for this algorithm in terms of n ?

SequentialSearch(a,x,n)
{
    i=n;
    a [0]=x;
    while(a [i]!= x) do
        i = i-1
    return i
}

Please mention the count for each step here.Thanks!

Upvotes: 2

Views: 8392

Answers (3)

samaksh shrivastava
samaksh shrivastava

Reputation: 99

procedure for finding step count

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)

Upvotes: 3

Sazzadur Rahaman
Sazzadur Rahaman

Reputation: 7126

Here is the analysis of your step count:

SequentialSearch(a,x,n)
{
   i=n;    // 1 assignment operation 
   a [0]=x; // 1 assignment operation 
    while(a [i]!= x) do  // n number of comperison (worst case)
       i = i-1 // n number of decrement operation (worst case)
    return i // 1 return 
}

In worst case you have: 2n + 3 number of operations. As your number of operation is linearly related your input array size (n), in worst case. So the runtime complexity of the algorithm is O(n).

Upvotes: 1

Exceptyon
Exceptyon

Reputation: 1582

I hope this is what you are looking for:

while (a[i] != x) i = i-1;

worst case: will scan the whole array, from a[n] to a[0] = O(n)

mean case: will scan half array O(n/2) = O(n)

complexity is O(n)

Upvotes: 1

Related Questions