CODEWITHSUNDEEP
algorithm
Saffor
Saffor

Reputation: 60

How do I calculate the runing time of the following algorithm?

Question : Analyse the ruunnig time of the following algorithm ? T(n)=Cop * C(n)

flag=false;
count=0;
for(i=0;i<=n;i++)
{
    if (A[i]==1)
        count++;
    flag=true;
}
else
    flag=false;
return(count);

What is the total time? Suppose n = 50 .

Upvotes: 0

Views: 78

Answers (2)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186668

If you format out the code, you'll find out that it doesn't compile. You, probably, mean something like this (please, notice, that assigning flag within the loop is of no use: you have to check the last item only) 

flag = false;
count = 0;

for(i = 0; i <= n; i++) 
  if (A[i] == 1) {
    count++;

    flag = true;
  }
  else
    flag = false;

return(count);

A better implementation:

count = 0;

for(i = 0; i <= n; i++) 
  if (A[i] == 1) 
    count += 1;

flag = (n >= 0) && (A[n] == 1);

So far so good, if A is large enough (A.Length > n) you have O(n) time complexity, so the execution time can be approximated by linear function:

t = k * n + b

where k and b are constants (specific to the workstation, compiler, OS etc.) which can be derived from the experiments.

Upvotes: 1

Codor
Codor

Reputation: 17595

In the current form, the runtime complexity of the algorithm (which is what the question is apparently about) would be

O(n)

where n is the number of elements in A which are to be processed.

Upvotes: 1

Related Questions